A new question: every pair at once
The last three guides all answered the same shape of question: fix one start vertex, and find the shortest path from it to everywhere else. That is the single-source problem, and relaxation solved it — Dijkstra when weights are non-negative, Bellman-Ford when some go negative. But many real tasks ask something bigger: the shortest distance between every pair of vertices. Think of a road network where you want a full distance table between all towns, or a routing matrix where every node needs its cost to every other node. This is the all-pairs shortest paths problem, and it deserves its own algorithms.
The lazy answer is: just run a single-source algorithm n times, once from each vertex as the source. That works, and on the right graph it is even the best plan — hold that thought, it returns as Johnson's algorithm. But running Bellman-Ford from every source costs n times O(V*E), which on a dense graph (where E is around n^2) climbs to O(n^4). For dense graphs that is wasteful, and worse, it throws away an elegant structure that the all-pairs problem has and the single-source problem does not. Floyd-Warshall exploits exactly that structure.
Floyd-Warshall: the intermediate-vertex idea
Floyd-Warshall is a dynamic program, and its whole genius is the variable it builds the table over. Number the vertices 1 to n. Now define a sub-question: what is the shortest path from i to j *if the only vertices the path is allowed to pass through in the middle are drawn from {1, 2, ..., k}*? Call that distance d(i, j, k). The endpoints i and j are always allowed; the restriction is purely on which vertices may serve as stepping stones in between. We are going to grow k from 0 up to n, slowly unlocking more and more vertices as permissible intermediates.
Why is this the right variable? Because it gives a clean recurrence. Consider the shortest i-to-j path that may use intermediates from {1, ..., k}. There are exactly two cases for what it does with vertex k. Either the path does not use k at all — then it only uses intermediates from {1, ..., k-1}, so its length is just d(i, j, k-1). Or it does use k, exactly once (using it twice would mean a cycle through k, which without negative cycles never helps). Then the path splits cleanly into a best i-to-k piece and a best k-to-j piece, each itself only allowed to use intermediates from {1, ..., k-1}. So its length is d(i, k, k-1) + d(k, j, k-1). The true answer is the smaller of the two.
d(i, j, 0) = weight(i, j) if edge i->j exists, else +infinity (and 0 if i == j)
d(i, j, k) = min( d(i, j, k-1), # path avoids vertex k
d(i, k, k-1) + d(k, j, k-1) # path routes through k
)Turn that recurrence into a bottom-up table and the code is almost shockingly small: three nested loops, with k on the outside and i, j inside. The outer k-loop is what enforces the recurrence's dependency — when you process layer k, every entry you read on the right-hand side was finalized in layer k-1. With a clever in-place trick you can even drop the third dimension and update a single n-by-n distance matrix in place; it can be shown that overwriting is safe because the entries in row k and column k do not change during round k. The result is the entire algorithm in a few lines.
Why it is correct, what it costs, and a free bonus
The correctness is a clean induction on k. The inductive hypothesis is that after round k, every entry d(i, j) equals the true shortest i-to-j distance using only intermediates from {1, ..., k}. Base case k = 0 holds because with no intermediates allowed the only paths are single edges, which is exactly the initial matrix. The inductive step is the case analysis we just did: any shortest path restricted to {1, ..., k} either skips k (covered by the old value) or uses k once and splits at it (covered by the sum), and the min over those two is correct by the hypothesis applied to layer k-1. When k reaches n, all vertices are permitted intermediates, so d(i, j) is the unrestricted shortest distance — which is what we wanted.
The cost is easy to read straight off the loops: three nested loops each running over n vertices, with O(1) work inside, gives Theta(n^3) time. Space is Theta(n^2) for the distance matrix (the in-place trick removed the k-dimension). Notice something liberating: the running time does not depend on the number of edges at all, and it does not care whether weights are negative. The same flat triple loop handles a sparse graph and a dense graph identically. That edge-insensitivity is exactly why Floyd-Warshall is the natural choice for dense graphs — when E is already near n^2, you cannot do much better than n^3 anyway, and you get every pair in one tidy sweep.
Johnson: re-weight so Dijkstra becomes legal
Theta(n^3) is fine for dense graphs, but on a sparse graph it is overkill. If E is much smaller than n^2 — a road map where each town connects to only a handful of neighbors — we would love to run Dijkstra from each of the n sources, since each Dijkstra costs only O(E log V). That would give O(n*(E log V)), far below n^3 when E is small. The catch is brutal and familiar: Dijkstra is simply wrong with negative edge weights. So the dream of running it n times collapses the moment a single negative edge appears. Johnson's algorithm is the rescue — it makes all the weights non-negative without changing which path is shortest, and only then unleashes Dijkstra n times.
The naive idea — "just add a big constant to every edge so none is negative" — is a classic trap, and it is worth seeing exactly why it fails. Adding a constant c to every edge adds c per edge, so a path with more edges gets penalized more than a path with fewer. That can flip which path is shortest: a long cheap path can lose to a short expensive one. Johnson's trick is subtler. Assign each vertex v a number h(v), a "potential" or height, and re-weight each edge u-to-v from w(u, v) to w'(u, v) = w(u, v) + h(u) - h(v). Now sum the new weights along any path from s to t: the intermediate h-terms telescope and cancel, leaving total' = total + h(s) - h(t). Every s-to-t path shifts by the same amount h(s) - h(t), so their ordering is untouched — the shortest stays the shortest.
So any choice of potentials preserves shortest paths. The remaining magic is choosing h so that every re-weighted edge is non-negative, i.e. w(u, v) + h(u) - h(v) >= 0, which rearranges to h(v) <= h(u) + w(u, v). That inequality should look intensely familiar: it is exactly the triangle inequality that shortest-path distances always satisfy. So if we let h(v) be the shortest distance to v from some source, the re-weighting is guaranteed non-negative. Johnson does precisely this: add a brand-new vertex q with a zero-weight edge to every vertex, run Bellman-Ford once from q to get h(v) = dist(q, v) for all v (Bellman-Ford because these edges may be negative), and use those as the potentials.
- Add a dummy vertex q joined to every other vertex by an edge of weight 0; run Bellman-Ford from q. If it reports a negative cycle, stop — the problem is ill-defined.
- Set h(v) = dist(q, v) for every vertex v. These potentials satisfy the triangle inequality, so they will make every edge non-negative.
- Re-weight every edge: w'(u, v) = w(u, v) + h(u) - h(v). Now all weights are non-negative and shortest paths are unchanged.
- Run Dijkstra from each of the n vertices on the re-weighted graph. Convert each result back: true dist(u, v) = dist'(u, v) - h(u) + h(v).
Choosing between them, honestly
Add up Johnson's bill: one Bellman-Ford is O(V*E), then n runs of Dijkstra at O(E log V) each, totalling O(V*E log V). On a sparse graph where E is roughly n, that is about O(n^2 log n) — comfortably below Floyd-Warshall's n^3. On a dense graph where E is roughly n^2, Johnson degrades to about O(n^3 log n), now worse than Floyd-Warshall by a log factor and far more code to get right. So the honest rule of thumb is: sparse graph with possible negative edges, reach for Johnson; dense graph, reach for Floyd-Warshall. And if the weights are all non-negative to begin with, you can skip Johnson's Bellman-Ford preprocessing entirely and just run Dijkstra n times directly.
Remember the perennial honesty about asymptotics: these are scaling laws for large graphs, not a verdict at every size. The constant factor hidden in Floyd-Warshall's triple loop is tiny — it is three loops and a min — while Johnson carries the overhead of a priority queue, Bellman-Ford, and the re-weighting bookkeeping. On a small or only moderately sparse graph, the simple n^3 sweep can easily beat the asymptotically faster Johnson. "Faster on paper" is a statement about growth, not a guarantee for your particular input.
Step back and see the unity. Floyd-Warshall takes the all-pairs problem head-on as a single dynamic program over which intermediate vertices are allowed — a genuinely different idea, not just relaxation repeated. Johnson, by contrast, is pure composition: it reuses Bellman-Ford and Dijkstra exactly as the earlier guides built them, gluing them with one transformation that turns a hard graph (negative edges) into an easy one (non-negative) while preserving the answer. That re-weighting-by-potentials trick — shifting every quantity by a per-vertex height so a telescoping cancellation cleans up the structure — is a deep, reusable idea that reappears across optimization. Both algorithms are worth carrying forward: one a self-contained gem, the other a masterclass in standing on the shoulders of the tools you already trust.