Weighted shortest paths — Dijkstra and friends

BFS finds the fewest edges. With weights, the cheapest route may take more of them. That is Dijkstra's territory.

Dijkstra

Always expand the unvisited vertex with the smallest known distance — which is exactly what a min-heap gives you.

function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const heap = new MinHeap((a, b) => a[0] - b[0]);    // [distance, node]
  heap.push([0, start]);

  while (heap.size) {
    const [d, node] = heap.pop();

    if (d > (dist.get(node) ?? Infinity)) continue;   // stale entry, already improved

    for (const [next, weight] of graph.get(node) ?? []) {
      const candidate = d + weight;

      if (candidate < (dist.get(next) ?? Infinity)) {
        dist.set(next, candidate);
        heap.push([candidate, next]);
      }
    }
  }

  return dist;
}

O((V + E) log V) with a binary heap. The stale-entry skip is the lazy alternative to decreaseKey, and it is what most production implementations do.

Dijkstra requires non-negative weights. With a negative edge, a vertex already finalised might later be improved, and the algorithm has no way to revisit it.

Choosing the right algorithm

Bellman-Ford relaxes every edge V−1 times; if a V-th pass still improves something, a negative cycle exists — which is how arbitrage detection in currency exchange works.

Floyd-Warshall is three nested loops and fits on a napkin — worth memorising for small dense graphs:

for (const k of nodes)
  for (const i of nodes)
    for (const j of nodes)
      dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

A* adds a heuristic estimate of the remaining distance. With an admissible heuristic — never an overestimate — it finds the same optimal path while exploring far less. Straight-line distance in map routing is the standard example.

The habit to build

Before writing any pathfinding code, ask: are the edges weighted, can weights be negative, do I need one source or all pairs? Those three answers name the algorithm before you write a line.