Find the shortest route through a graph

Choose the right meaning of shortest

Breadth-first search explores one hop at a time. It finds a path with the fewest edges when every edge has equal cost. It does not find the fastest route if roads have different travel times. State that assumption in your campus-map interface.

Keep cycles bounded

Mark a node seen when you enqueue it. A cycle such as library to cafe to library should not repeat forever. This small version copies paths for clarity; large graphs should store parent pointers and reconstruct the result at the end.

Build the next version

Add six campus stops and display the returned path as a list. Test two equal-length routes and explain that either may be valid. Explore TheAlgorithms JavaScript repository to compare other search algorithms before adding weighted edges.

Try it yourself

function shortestPath(graph, start, goal) {
  const queue = [[start]], seen = new Set([start]);
  for (let i=0; i<queue.length; i++) {
    const path = queue[i], node = path.at(-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({library:["cafe","lab"],cafe:["gate"],lab:["gate"],gate:[]},"library","gate"));

Enable JavaScript for this interactive activity. You can read all lesson explanations above without it.