🔹.findShortestPath()
data structure ⟩ graph ⟩ .findShortestPath()
find a shortest path between two nodes using breadth-first search.
null if not found.
replit > Graph (js)
// ⭐ Graph
class Graph {
// omitted ...
// 🔹 .findShortestPath()
// - use breadth-first search
findShortestPath(start, target, { debug = false }={}) {
const queue = new Queue(); // (queue) nodes to visit
const path = Object.create(null); // (dict) save paths to nodes (self included)
// put `start` node into queue
queue.enqueue(start);
path[start] = [start]; // save path to `start`
// while queue is not empty
while (!queue.isEmpty) {
// debug (omitted ...)
// pick first node (front) from queue
const front = queue.dequeue();
// if target is found, return path.
if (front === target) return path[front];
// else add unexplored neighbors to queue
const unexplored = this
.neighborsOf(front)
.filter(node => !queue.isExplored(node));
for (let child of unexplored) {
queue.enqueue(child);
path[child] = path[front].concat(child); // save path to child
}
}
// queue is empty, no possible path.
return null;
}
}
graph.findShortestPath('G', 'C') // [ 'G', 'F', 'M', 'P', 'A', 'C' ]
Last updated