JavaScript: breadth-first search for the fewest steps

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.

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

Read the full lesson