Shortest paths

Why BFS is not enough

BFS counts steps. The moment an edge can cost 2 and another 9, fewest-steps and cheapest stop being the same question, and BFS answers the wrong one.

Dijkstra’s fix is one change: instead of taking the oldest node from the frontier, always take the cheapest one. A queue becomes a priority queue, and that is the whole algorithm.

        a
      2/  \9
      b     c
      1\   /1
         d              a → c → d costs 10 and is TWO steps
                        a → b → d costs 3  and is two steps

BFS finds whichever it reaches first. Both are "two steps".

The algorithm

Pushing a duplicate instead of updating the heap is the standard trick. A binary heap cannot cheaply decrease a key, so the same node may sit in it several times at different costs; the cheapest comes out first, and the later copies are skipped by the done check. It costs a little memory and removes a great deal of complexity.

function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const cameFrom = new Map([[start, null]]);
  const done = new Set();
  const heap = new MinHeap((entry) => entry.cost);

  heap.push({ node: start, cost: 0 });

  while (heap.size) {
    const { node, cost } = heap.pop();
    if (done.has(node)) continue;           // a stale copy — see below
    done.add(node);                         // this node's distance is now FINAL

    for (const edge of graph.get(node) ?? []) {
      const next = cost + edge.cost;
      if (next < (dist.get(edge.to) ?? Infinity)) {
        dist.set(edge.to, next);
        cameFrom.set(edge.to, node);
        heap.push({ node: edge.to, cost: next });   // push again, do not update
      }
    }
  }

  return { dist, cameFrom };
}

Why taking the cheapest first is enough

When a node comes off the heap it is the cheapest unfinished node anywhere. Any other route to it would have to go through some other unfinished node — which is at least as expensive — and then travel further. Since no edge can reduce a total, that route cannot be cheaper. So the first time a node is popped, its distance is final.

Read that argument again with the phrase "no edge can reduce a total" in mind, because it is the assumption that breaks.

Negative weights break it

With a negative edge, a longer route can become cheaper later, so "finalised" is no longer safe and the answer is simply wrong — not slower, wrong. Use Bellman–Ford (O(n·e), and it detects negative cycles) when weights can be negative.

Negative weights are rarer than they sound but not exotic: currency arbitrage, a rebate, an energy gain in a game, a score you are maximising rather than a cost you are minimising.

    a --1--> b
    |        |
    4       -3
    v        v
    c <------+          a → b → c costs -2, but Dijkstra finalises c at 4 first

The family

A* is the one worth knowing about: change the heap priority from cost to cost + estimateToGoal and, provided the estimate never overestimates, you get the same guaranteed answer while exploring a fraction of the graph. Every game pathfinder and every route planner is this.