JavaScript: breadth-first search for the fewest steps
Find a shortest path in an unweighted graph by exploring it layer by layer.
On this page
JavaScript arrays, objects, and Set.
- Find a shortest path in an unweighted graph by exploring it layer by layer.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Breadth-first search (BFS) explores a graph in layers: first the start, then all nodes one edge away, then two edges away, and so on. It uses a first-in, first-out queue. If every edge has the same cost, the first path that reaches the goal has the fewest edges.
The queue here holds whole paths, so the answer is available the moment the goal is dequeued. A Set of visited nodes stops the search from walking in circles and from queueing a node twice. A goal that cannot be reached makes the queue run empty, and the function returns null.
Code example
const graph = {
A: ["B", "C"],
B: ["D"],
C: ["D", "E"],
D: ["F"],
E: ["F"],
F: [],
};
function shortestPath(start, goal) {
const queue = [[start]];
const seen = new Set([start]);
while (queue.length > 0) {
const path = queue.shift();
const node = path[path.length - 1];
if (node === goal) return path;
for (const next of graph[node]) {
if (!seen.has(next)) {
seen.add(next);
queue.push([...path, next]);
}
}
}
return null;
}
console.log(shortestPath("A", "F").join(" -> "));
console.log(shortestPath("F", "A"));A -> B -> D -> F null
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
const graph = { A: ["B", "C"], B: ["D"], C: ["D", "E"], D: ["F"], E: ["F"], F: [],}; function shortestPath(start, goal) { const queue = [[start]]; const seen = new Set([start]); while (queue.length > 0) { const path = queue.shift(); const node = path[path.length - 1]; if (node === goal) return path; for (const next of graph[node]) { if (!seen.has(next)) { seen.add(next); queue.push([...path, next]); } } } return null;} console.log(shortestPath("A", "F").join(" -> "));console.log(shortestPath("F", "A"));Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The queue starts with the one-node path [A]. | queue = [[A]] | — | |
| Take the oldest path; shorter paths always come out before longer ones. | queue = [[A]] | — | |
| The first time the goal is reached, this is a shortest path. | queue = [[A]] | — | |
| A→B→D→F has three edges; A→C→D→F and A→C→E→F also have three. | queue = [[A]] | A -> B -> D -> F | |
| F has no outgoing edges, so A is unreachable and the function returns null. | queue = [[A]] | A -> B -> D -> F null |
Behind the scenes
How JavaScript processes this code
A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.
Cost and common mistakes
O(V + E) time for V nodes and E edges, ignoring the cost of copying paths.
- Array.shift() is O(n) on a long array. For big graphs use an index pointer or a real queue.
- Marking nodes as seen only when dequeued allows duplicates in the queue.
- BFS finds the fewest edges, not the lowest total cost. For weighted edges use Dijkstra's algorithm.
Try it yourself
Are there other shortest paths from A to F?
Reveal answer and reasoning
Yes: A → C → D → F and A → C → E → F, both also with three edges. BFS returns the first one it finds.