JavaScript: breadth-first search for the fewest steps

Find a shortest path in an unweighted graph by exploring it layer by layer.

JavaScript

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"));

Output

A -> B -> D -> F
null

Explanation

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.

Explore the dry run

Guided walkthroughReady

1const graph = {

2 A: ["B", "C"],

3 B: ["D"],

4 C: ["D", "E"],

5 D: ["F"],

6 E: ["F"],

7 F: [],

8};

10function shortestPath(start, goal) {

11 const queue = [[start]];

12 const seen = new Set([start]);

13 while (queue.length > 0) {

14 const path = queue.shift();

15 const node = path[path.length - 1];

16 if (node === goal) return path;

17 for (const next of graph[node]) {

18 if (!seen.has(next)) {

19 seen.add(next);

20 queue.push([...path, next]);

21 }

22 }

23 }

24 return null;

25}

27console.log(shortestPath("A", "F").join(" -> "));

28console.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

Prepared trace of the published program. Some rows group repeated iterations.
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

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.

JavaScript: breadth-first search for the fewest steps

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading