Shortest Paths with Dijkstra

We already tackled an algorithm that finds shortest paths, BFS. The problem is that it only counts hops, but in the real world some edges can be more expensive than others i.e., we need a way to find the shortest path with these weights accounted for.

The solution

Give every node a best-known distance. The source gets 0, because standing still is free. Everything else gets infinity, which is just a way of writing "no route found yet". Then repeat two steps until you run out of nodes.

1. Among the nodes you have not finalised, take the one with the smallest best-known distance and mark it settled. By the argument above, its number is now permanent.

2. Look at each of that node's neighbors and ask a single question: is going through this node cheaper than the best route I currently know to that neighbor? If it is, write down the smaller number.

That second step is called relaxing an edge, a piece of vocabulary considerably more intimidating than the idea behind it. Relaxing edge u -> v means checking whether dist[u] + weight(u,v) is less than dist[v], and writing it down when it is. The name comes from picturing each distance as a stretched constraint that you let settle to a lower value once you find one.

A full trace, by hand

Reading the two rules is not the same as believing them. Below is the graph every round in this section runs on, five nodes and six weighted edges. Click a node to try it yourself, or just read on: every number below is worked out by hand next.

Everything starts unknown except the source itself.

A has the smallest number, so A settles at 0. Relaxing its two edges gives B a route costing 2 and C a route costing 5.

The smallest unsettled number is now B at 2, so B settles. From B you can reach C for 2 plus 1, which is 3. That beats the 5 you had, so C drops to 3. You can also reach D for 2 plus 7, which is 9, and 9 beats infinity, so D becomes 9.

C is now the smallest unsettled node at 3, so it settles. From C you reach D for 3 plus 2, which is 5, and that beats the 9 you wrote a moment ago, so D improves to 5. This is the moment worth pausing on. D's value changed after it had already been discovered. Discovery and certainty are different things.

D settles at 5 and hands E a route of 5 plus 3, which is 8. Then E settles at 8 and there is nothing left to do.

Look back at D. It was 9, then 5, then final. Had you settled D the first time you saw a number for it, you would have shipped an answer nearly twice the true cost. The rule that saves you is not "settle a node when you reach it" but "settle a node when it is the cheapest thing left anywhere in the graph".

Now drive it yourself

The number floating above each node is its best-known distance. Watch the numbers fall from infinity as better routes turn up, and watch the panel record which ones have been locked in. Try starting from a different node, and predict the first two settlements before you press play.

Try this other, more complicated one:

Getting the actual route

| Whenever you improve a node's distance, also record which node you came from.

To read the route to E, start at E, jump to its recorded predecessor, and keep jumping until you land on the source, then reverse what you collected. The predecessors form a tree rooted at the source containing a shortest path to every reachable node, which is a lot of value for one array.

if (dist[u] + w < dist[v]) {
  dist[v] = dist[u] + w;
  parent[v] = u;          // the only new line
}

function pathTo(target) {
  const route = [];
  for (let at = target; at !== undefined; at = parent[at]) route.push(at);
  return route.reverse();
}

Where the running time comes from

It is worth deriving the cost rather than memorising it, because the derivation tells you which implementation to reach for.

Each of the V nodes settles exactly once, and settling means finding the smallest remaining number. Each of the E edges is relaxed once, when the node at its tail settles. So the total work is V smallest-finds plus E relaxations, and everything depends on how fast those two operations are.

The array version wins on dense graphs, where E approaches V squared and the scan cost is swamped anyway. The heap wins on sparse graphs, which covers most real road and network data. If you only ever remember one version, remember the heap.

One practical detail trips people up. Most heap implementations cannot cheaply lower a key that is already inside, so the usual trick is to push the improved entry and leave the stale one in place. When a stale entry surfaces later its distance no longer matches the node's current best, so you skip it. That is the if (d > dist[u]) continue; line in the code below. Without it the algorithm still terminates, but it repeats work it has already done.

Negative Weights?

Go back to the argument that made all of this work. It relies on the fact that extra edges can never reduce a total. The thing is, there are definitely some scenarios where a negative weight makes sense, like when there are benefits to taking a route.

Take this for example

Dijkstra settles A at 0, then looks around and sees B at 4 and C at 3, so it picks C which costs 3 in total. This is more expensive then if it went to B then C for a total of 2.

Notice that this is not a bug in some edge case of the implementation. It is just something Dijkstra's algorithm doesn't cover, which is why the fix is a different algorithm rather than a patch. Bellman-Ford drops the idea of settling nodes in a fixed order and relaxes every edge repeatedly instead. That costs more but it still works even for negative gates.

Mistakes worth knowing about in advance

Settling a node the moment you first reach it. This is the most common error by a wide margin, and the trace above shows the damage: D was discovered at 9 and finished at 5. A node is only safe to settle once it is the cheapest unsettled node in the graph.

Running it on negative edges because the answer looked plausible. Dijkstra does not crash on negative weights. It returns a confident wrong number, which is worse. Check the weights before you choose the algorithm.

Forgetting the stale-entry check with a heap. Without the skip, old entries get processed again carrying distances that are no longer current. On large graphs that turns into a real slowdown.

Assuming unreachable means zero. Nodes with no route from the source keep their infinity. Initialize with a value you can recognize afterwards, and never with 0.

The implementation

Nothing here should surprise you now. The only line doing real thinking is the comparison inside the inner loop.

function dijkstra(graph, source) {
  const dist = new Map();
  const parent = new Map();
  for (const node of graph.nodes) dist.set(node, Infinity);
  dist.set(source, 0);

  const heap = new MinHeap();       // ordered by distance
  heap.push([0, source]);

  while (!heap.isEmpty()) {
    const [d, u] = heap.pop();
    if (d > dist.get(u)) continue;  // a stale entry, already improved on

    for (const { to, weight } of graph.neighbors(u)) {
      const candidate = dist.get(u) + weight;
      if (candidate < dist.get(to)) {
        dist.set(to, candidate);
        parent.set(to, u);
        heap.push([candidate, to]);
      }
    }
  }

  return { dist, parent };
}

Check yourself