One move, many algorithms
On the graph-search rung you walked a graph by counting edges: breadth-first search found the fewest-hop route because every step had the same cost. Now we add weights — a distance, a toll, a travel time on each edge — and ask for the cheapest route, where 'cheapest' means least total weight, not fewest edges. A three-edge detour of weight 1 each beats one heavy edge of weight 10. This is the single-source shortest-path problem: from one source vertex, find the least-cost route to every other vertex at once. The remarkable thing about this whole rung is that every algorithm for it — Dijkstra, Bellman-Ford, the DAG sweep — is built from one operation repeated in a clever order.
That operation is edge relaxation, and it is almost embarrassingly small. Keep an array d where d[v] is your current best guess of the distance from the source to v. Look at a single edge from u to v with weight w, and ask one question: 'If I travel to u and then take this edge, is that cheaper than my current guess for v?' If d[u] + w is less than d[v], lower d[v] to d[u] + w. That is the entire move — one comparison and maybe one assignment. Relaxing an edge can only lower an estimate, never raise it, and an edge that is already as good as it can be simply leaves d unchanged. Everything in this rung is variations on the question of which edges to relax, and in what order.
relax(u, v, w): # try the shortcut: source -> ... -> u -> v
if d[u] + w < d[v]:
d[v] = d[u] + w # found a cheaper known path to v
pred[v] = u # remember the road we came in onWhy relaxation is always safe
Before worrying about order, settle a more basic worry: could relaxing make things wrong? Here is the load-bearing invariant, exactly the kind of loop invariant you proved on the correctness rung. At every moment, d[v] is the length of some real path from the source to v (and infinity if you have not yet found any path). It is never a fantasy number — it is always achievable by an actual route you have already discovered. Therefore d[v] is always an over-estimate: it can equal the true shortest distance, but it can never dip below it, because there is no path shorter than the shortest one.
- Initialization: set d[source] = 0 (the empty path, length 0) and d[v] = infinity for everyone else. The invariant holds — 0 is a real path's length, and infinity honestly says 'no path found yet.'
- Maintenance: when relax(u, v, w) fires, the new d[v] = d[u] + w is the length of (a real path to u) followed by (the edge u->v) — itself a real path to v. So the invariant survives every relaxation.
- Consequence: because d[v] is always a real path's length, d[v] >= dist(v) at all times. Relaxation can only push d[v] down toward dist(v), never past it — so extra, out-of-order relaxations are wasted work, never errors.
This is a wonderfully forgiving situation. You cannot break correctness by relaxing edges you did not need to, or by relaxing them in a silly order — the worst that happens is you do useless work. That freedom is exactly why so many different algorithms can share one engine: they all converge to the same correct answer, and they compete only on how few relaxations they need to get there. Correctness is free; efficiency is the whole game.
When are you done? The triangle inequality
If relaxing can never overshoot, the only way to be wrong is to stop too early — to quit while some d[v] is still bigger than dist(v). So you need a stopping test. It comes from a piece of pure common sense called the triangle inequality: a detour can never be a bargain. For every edge (u, v) with weight w, the true distances satisfy dist(v) <= dist(u) + w. Why? The right side is the cost of one particular route to v — a best route to u, then the single edge to v — and dist(v) is the minimum over all routes, so it cannot exceed any single one of them.
Now translate that into a test on your estimates. An edge (u, v) is relaxable exactly when d[u] + w < d[v] — that is, exactly when d violates the triangle inequality for that edge. So 'no edge can be relaxed any further' is the same statement as 'd satisfies the triangle inequality everywhere.' And there is a theorem: once d[v] is finite for every reachable v and no edge is relaxable, then d[v] = dist(v) for all v. A relaxable edge is a flaw you can see and fix; when there are no flaws left, the estimates have nowhere left to fall, and an over-estimate with nowhere to fall must already be exact. That single equivalence — relaxable edge equals violated triangle inequality — is the convergence test underneath every algorithm in this rung.
A tiny trace you can do by hand
Take four vertices s, a, b, t with edges s->a (4), s->b (1), b->a (2), a->t (3), b->t (7). Start with d[s] = 0 and everyone else at infinity. Relax s's edges: d[a] becomes 4, d[b] becomes 1. Now relax b's edges: b->a tries 1 + 2 = 3, which beats the current 4, so d[a] drops to 3 (and pred[a] becomes b); b->t tries 1 + 7 = 8, so d[t] becomes 8. Finally relax a's edge a->t: 3 + 3 = 6 beats 8, so d[t] falls to 6, with pred[t] = a.
Check the stopping test: is any edge still relaxable? d[a] = 3 came via b, and 0 + 4 = 4 is not less than 3, so s->a is fine; every other edge likewise satisfies d[u] + w >= d[v]. No edge violates the triangle inequality, so we are done, and the answers are final: dist(a) = 3, dist(b) = 1, dist(t) = 6. Notice the cheapest way to a was the two-edge route s->b->a (cost 3), not the direct edge of weight 4 — 'shortest' really did mean least total weight. Notice too that the order mattered for speed: relaxing a's edge before b's would have set d[t] using the stale d[a] = 4 first, then needed a second fix. Different orders, same final answer.
Order is everything — and a tree for free
Since correctness is automatic, the design problem reduces to one question: which order of relaxations reaches the no-relaxable-edge state with the least work? That single question is what splits this rung into separate algorithms. The blunt answer is Bellman-Ford: just relax every edge, over and over, V-1 times — slow at O(V*E), but it cannot miss, and it even survives negative weights. The clever answer, when all weights are non-negative, is Dijkstra's algorithm: always finalize the closest unfinished vertex next, which lets every edge be relaxed just once. And on a directed acyclic graph, relaxing in topological order finishes in a single linear sweep. Same atom, three orders, three running times.
There is a reason no order can do better than 'relax every edge on a shortest path at least once, in the right sequence.' Shortest paths have optimal substructure: any subpath of a shortest path is itself shortest. If the cheapest route to t passes through a, then the piece from the source to a inside that route must itself be a cheapest route to a — otherwise you could swap in a cheaper piece and beat the supposedly-best route to t, a contradiction. This is the same optimal-substructure idea behind dynamic programming, and it is why relaxing edges in the right order works at all: each correct distance is built from a smaller correct distance plus one final edge.
One last gift falls out of the pred pointers we have been quietly recording. Every time a relaxation lowers d[v], we set pred[v] = u — the road we arrived on. At the end, those predecessor edges link up into a shortest-path tree rooted at the source: follow pred from any vertex back to s, reverse it, and you have an actual cheapest route, not just its cost. GPS needs the route, not only the mileage, and this tree delivers every route at once because optimal substructure lets shared prefixes be shared branches. (Do not confuse it with a minimum spanning tree, the subject of guide 5 — that one minimizes total edge weight and has no source at all; the two trees solve different problems and usually look different.) With relaxation, the invariant, the triangle-inequality stopping test, and this tree in hand, you are ready to meet the specific algorithms — starting with Dijkstra, and why it cannot tolerate a single negative edge.