Shortest Paths with Dijkstra
We already tackled how BFS can be used to find the shortest paths. The limitation is that each edge is as costly as all other edges, which is often not the case in real life. Dijkstra's algorithm helps us find the shortest path when some edges are more expensive to traverse than others.
The solution
Give every node a best-known distance, with 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 the following steps:
- Among the nodes you have not finalised, take the one with the smallest best-known distance and mark it settled.
- Look at each of that node's neighbors and ask if 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. Relaxing edge u -> v means checking whether dist[u] + weight(u,v) is less than dist[v], and writing it down if 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.
Full walkthrough
Below is the graph every round in this section runs on, five nodes and six weighted edges. Click a node to try it yourself, and check the full walkthrough.
Click any node to route from it instead. Currently starting at A.
Every node starts at infinity because we haven't found any route to it yet. A is the exception: it costs nothing to stand where you already are, so it starts at 0.
Cheapest known costfrom A
Why it never revisits. Any other route to a locked node would have to leave through one that already costs more, and no weight is negative, so it can only get worse from there.
Everything starts unknown except the source itself.
| Round | A | B | C | D | E | Settled this round |
|---|---|---|---|---|---|---|
| start | 0 | inf | inf | inf | inf | nothing yet |
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.
| Round | A | B | C | D | E | Settled this round |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 5 | inf | inf | A at 0 |
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.
| Round | A | B | C | D | E | Settled this round |
|---|---|---|---|---|---|---|
| 2 | 0 | 2 | 3 | 9 | inf | B at 2 |
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.
| Round | A | B | C | D | E | Settled this round |
|---|---|---|---|---|---|---|
| 3 | 0 | 2 | 3 | 5 | inf | C at 3 |
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.
| Round | A | B | C | D | E | Settled this round |
|---|---|---|---|---|---|---|
| 4 | 0 | 2 | 3 | 5 | 8 | D at 5 |
| 5 | 0 | 2 | 3 | 5 | 8 | E at 8 |
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".
More example
The number floating above each node is its best-known distance. Try starting from a different node, and predict the first two settlements before you press play.
Click any node to route from it instead. Currently starting at A.
Every node starts at infinity because we haven't found any route to it yet. A is the exception: it costs nothing to stand where you already are, so it starts at 0.
Cheapest known costfrom A
Why it never revisits. Any other route to a locked node would have to leave through one that already costs more, and no weight is negative, so it can only get worse from there.
Try this other, more complicated one:
Click any node to route from it instead. Currently starting at A.
Every node starts at infinity because we haven't found any route to it yet. A is the exception: it costs nothing to stand where you already are, so it starts at 0.
Cheapest known costfrom A
Why it never revisits. Any other route to a locked node would have to leave through one that already costs more, and no weight is negative, so it can only get worse from there.
Getting the actual route
Idea
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.
| Finding the minimum | One find | One relaxation | Total |
|---|---|---|---|
| Scan the whole array | O(V) | O(1) | O(V squared) |
| Binary heap | O(log V) | O(log V) to push | O((V + E) log V) |
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.
Tip
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, which negative edges violates.
Take this for example
Click any node to route from it instead. Currently starting at A.
Every node starts at infinity because we haven't found any route to it yet. A is the exception: it costs nothing to stand where you already are, so it starts at 0.
Cheapest known costfrom A
Why this run cannot be trusted. Locking a node in is only safe when no later route can undercut it, and that needs every weight to be non-negative. This graph has one that is not, so a locked number here may simply be wrong, and Dijkstra has no way to notice.
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
Why is it safe to permanently settle the unsettled node with the smallest distance?