All-Pairs Shortest Paths

The single-source lesson found the shortest path from ONE source to everywhere. This lesson finds the shortest path between EVERY pair of vertices at once. By the end you will be able to implement and animate extendShortestPaths and the matrix-multiplication view (slowAllPairsShortestPaths and fasterAllPairsShortestPaths), floydWarshall with its D and Π matrices, transitiveClosure, and Johnson's reweighting algorithm for sparse graphs — and know exactly when negative-weight cycles break each method and how each method notices.

The all-pairs problem: W, D, Π

Imagine a delivery company with n warehouses. The single-source lesson answered "what is the cheapest route from warehouse 0 to everywhere else?". This lesson answers the harder question every dispatcher actually needs: "what is the cheapest route between every pair of warehouses?" — all n² answers, computed together, sharing work instead of running a single-source algorithm n separate times from scratch.

The input is a weighted, directed graph G = (V, E) with a weight function w: E → ℝ (negative weights are allowed, as long as there is no negative-weight cycle reachable from a vertex that can also reach back to it). Vertices are numbered 0, 1, …, n−1, exactly like Dart list indices. The whole lesson represents the graph as an n × n weight matrix W = (w_ij):

w_ij = 0 if i = j, w(i,j) if (i,j) ∈ E, ∞ if (i,j) ∉ E and i ≠ j

Every algorithm in this lesson produces two matrices:

D = (d_ij), where d_ij = δ(i,j), the true shortest-path weight from i to j.
Π = (π_ij), the predecessor matrix: π_ij is the vertex right before j on a shortest i-to-j path (or null, shown as "–", if i = j or no path exists).

Given a row i of Π, printAllPairsShortestPath(Π, i, j) reconstructs the actual path by walking predecessors backward from j until it reaches i — the same idea as printing a path from a single-source π array in the graph-basics lesson, just reading from row i of Π. You will build and test exactly this reconstruction in the question bank.

Before you start — words used in this lesson. A directed graph is dots (vertices) joined by one-way arrows (edges); see the graph basics lesson. Each edge carries a number, its weight (a toll, a distance, a cost). A path is a chain of edges and its weight is the sum of its edge weights; a cycle is a path that ends where it started. The one-source versions of today's problem, Bellman-Ford and Dijkstra, are in the single-source lesson; the "fill a table, reuse smaller answers" style is dynamic programming. A matrix is a square grid of numbers where row i, column j answers a question about the pair (i, j). ∞ ("infinity") stands for "no such path", min means "keep the smaller", and δ(i,j) (delta) is the true shortest weight. A graph is sparse if it has few edges and dense if almost every pair of vertices has one. Θ(n³) ("theta of n cubed") means "grows like n × n × n" — three nested loops of n steps each.

A tiny example first. Three depots with one-way roads: 0→1 costs 2, 0→2 costs 7, 1→2 costs 3, 2→0 costs 4, 2→1 costs 1. The three grids below are computed live by this page's own Floyd-Warshall code (later sections animate how):

Read D, row 0, column 2: the cheapest cost from depot 0 to depot 2 is 5, not the direct 7, because 0→1→2 costs 2 + 3. Read Π, row 0, column 2: the value 1 means "the last stop before 2 on that cheapest route is depot 1".

A graph with a negative-weight cycle has no well-defined δ(i,j) for any pair the cycle can reach and be reached from (you could loop the cycle forever, making the "shortest" path weight −∞). Every algorithm below either assumes no negative cycle exists (extendShortestPaths, transitiveClosure), or actively detects one and reports it (the Floyd-Warshall diagonal check, Johnson's Bellman-Ford phase) — each example section below includes a dedicated negative-cycle demonstration so you see exactly how.

Why "all pairs" deserves its own algorithms: the answer alone has n² numbers, so no method can beat Ω(n²). The obvious baseline — run a one-source algorithm from every vertex — costs n × O(VE) = O(V²E) with Bellman-Ford (Θ(V⁴) on a dense graph) or n × Dijkstra when all weights are nonnegative. This lesson gets Θ(V³) even with negative weights (Floyd-Warshall) or beats that on sparse graphs (Johnson), by sharing work between the n sources.

Four words carry the whole lesson: W = the input (direct road costs), D = the answer (d_ij = δ(i,j)), Π = the memory of how (the vertex just before j), and negative-weight cycle = the only thing that can make "shortest" meaningless.

The maths as code. The weight matrix W and the size of the answer (n² numbers, so Ω(n²)) written as Dart.

Shortest paths and matrix multiplication

Define l_ij^(m) = the minimum weight of any path from i to j that uses at most m edges. With zero edges allowed, l_ii⁽⁰⁾ = 0 and every other l_ij⁽⁰⁾ = ∞ (you can't get anywhere in zero steps). Growing m by one means: either the best ≤(m-1)-edge path was already good enough, or the best path takes one more hop through some vertex k — try every k and keep the cheapest (the at-most-m-edges recurrence):

l_ij^(m) = min_{0≤k≤n−1} ( l_ik^(m-1) + w_kj )

Since every simple shortest path uses at most n-1 edges, δ(i,j) = l_ij^(n-1) = l_ij⁽ⁿ⁾ = l_ij⁽ⁿ⁺¹⁾ = … — going further never helps once you've reached n-1 edges.

The maths as code. The at-most-m-edges recurrence: L[m] is the "at most m edges" matrix, built by the recurrence, and it stops changing at m = n−1.

Side by side: matrix multiplication vs shortest paths

Ordinary matrix multiplication says: "for cell (i, j), pair up row i of the first grid with column j of the second, multiply each pair, then add the products". Shortest paths is the same dance in different clothes: pair up "cheapest cost to reach k" with "cost of the last hop k→j", add each pair (walk the first part, then hop), and keep the minimum — you want the cheapest single route, not the total of all routes.

Swap two operations and the "nothing" values that go with them, and every line of the ordinary matrix product becomes a line of extendShortestPaths:

Role	Ordinary product	Min-plus product (shortest paths)
combine one candidate	`a_ik · b_kj` (× )	`l_ik + w_kj` (+ )
collect all candidates	`Σ_k` (add up)	`min_k` (keep the smallest)
"nothing here" value (adding it changes nothing)	`0`, because x + 0 = x	`∞`, because min(x, ∞) = x
"do nothing" value (combining with it changes nothing)	`1`, because x · 1 = x	`0`, because x + 0 = x
identity matrix	1 on the diagonal, 0 elsewhere	0 on the diagonal, ∞ elsewhere (this is `L⁽⁰⁾`)
the m-th power of the matrix	`A^m`	`L^(m)` = cheapest routes using at most m edges

Small example first. For the tiny 3-depot graph, cell (0,2): the ordinary product adds 0·7 + 2·3 + 7·0 = 6 (with ∞ written as 0), the min-plus product takes min(0+7, 2+3, 7+0) = 5. Same three candidates k = 0, 1, 2; different operations. Watch both products fill in together:

Notice the right-hand grid of Example 1 is exactly L⁽²⁾ = W ⊙ W: every entry answers "cheapest route using at most 2 edges".

The analogy has one trap: a missing edge is the number 0 in the ordinary world (it adds nothing), but it must be ∞ in the shortest-path world. If you used 0 there you would be declaring a free teleport between unconnected cities, and every "shortest" path would collapse to 0. The animation writes the ∞ cells as 0 only in the left-hand grid, on purpose.

Why it matters that the analogy is exact: every fact about matrix multiplication that only relies on associativity and distributivity carries over unchanged (here + distributes over min: a + min(b, c) = min(a+b, a+c)). The big payoff is associativity, which is what lets us square the matrix below. Mathematicians call (min, +) the tropical semiring; the (OR, AND) pair used for transitive closure is the Boolean semiring.

Shortest paths with at most m edges is raising the weight matrix to the m-th power in the (min, +) world. Everything that follows — extend, slow, faster — is just "how fast can we compute a matrix power".

The maths as code. The ordinary matrix product next to the min-plus product, the identity matrix L⁽⁰⁾, associativity and distributivity (a + min(b, c) = min(a+b, a+c)) as numeric checks.

extendShortestPaths(L, W)

This recurrence is exactly the recurrence for ordinary matrix multiplication, with min replacing + and + replacing × (and ∞ replacing the "0" identity, since min(x, ∞) = x just like x + 0 = x). extendShortestPaths computes one such "product" L' = L ⊙ W, turning ≤(m-1)-edge estimates L into ≤m-edge estimates L':

Three nested loops over i, j, k, each doing O(1) work — exactly like the ordinary matrix product — so extendShortestPaths costs Θ(n³).

Small example first. With the tiny 3-depot graph and L = W: l'₀₂ = min(l₀₀+w₀₂, l₀₁+w₁₂, l₀₂+w₂₂) = min(0+7, 2+3, 7+0) = 5 — the two-edge route 0→1→2 (cost 5) beats the one-edge route (cost 7). The animations show every one of these trials:

Loop invariant: just before the assignment to l'_ij finishes trying vertex k, the running value of l'_ij equals min_k'≤k(l_ik' + w_k'j) — the best 1-more-edge path found among the first candidate intermediate vertices. After the last k, that minimum has been taken over all vertices, which is exactly the recurrence above.

Two classic bugs. (1) Using a big finite number such as 999999 for ∞: then 999999 + (−4) looks like a real route of cost 999995 and quietly beats "no route" — always test for ∞ before adding (the Dart code below does). (2) Writing the result into L itself while still reading it: entry l'_ij would then use already-updated neighbours and mix different edge budgets, so keep L' a separate matrix.

One extend call = one "matrix product": Θ(n³) time, it turns "at most m−1 edges" into "at most m edges" (when the second argument is W) or doubles the budget (when it is L itself, next).

In Dart every loop is for (int i = 0; i < n; i++) and double.infinity plays ∞.

Input size → what is feasible: n ≤ 100 → one call is n³ = 10⁶ steps (instant); n = 1000 → 10⁹ steps per call (seconds — roughly 1 to 10 s depending on the machine and implementation), and the all-pairs drivers need several calls, so switch to Floyd-Warshall.

slowAllPairsShortestPaths(W)

Chain extendShortestPaths starting from L⁽¹⁾ = W (paths using at most 1 edge are just direct edges), calling it n-2 more times to reach L^(n-1) = δ:

n-2 calls, each Θ(n³), give Θ(n⁴) total — correct, but wasteful.

Small example first. The tiny 3-depot graph has n = 3, so the loop for m from 2 to n−1 runs exactly once (m = 2): L⁽²⁾ = L⁽¹⁾ ⊙ W is already δ, and the extra check finds a diagonal of zeros.

The animations below add one extra check of our own to the plain procedure. Extend the diagonal check here too — after L^(n-1) do ONE more extend round (a negative simple cycle can use all n edges, so n-1 edges can miss it); then any l_ii < 0 means a negative-weight cycle passes through vertex i, and every δ(i,j) the cycle can reach and return from is really −∞, not the finite number shown.

Why stop at n−1 edges? With no negative-weight cycle, a shortest path never repeats a vertex (a repeat would be a cycle of weight ≥ 0 that you could cut out for free), so it has at most n vertices and therefore at most n−1 edges. That is why L^(n-1) = L⁽ⁿ⁾ = …. With a negative cycle the sequence never stops improving, which is exactly what the extra round detects.

SLOW = "n − 2 calls × Θ(n³) per call = Θ(n⁴)". It is the honest baseline that the next two sections beat.

Input size → what is feasible: n ≤ 30 → (n−2)·n³ = 28·27,000 ≈ 7.6·10⁵ steps is fine; n = 100 → 98·10⁶ ≈ 10⁸ is painful; n = 500 → 6·10¹⁰ is hopeless, use faster or Floyd-Warshall.

Repeated squaring → fasterAllPairsShortestPaths(W)

The extendShortestPaths "product" is associative (the question bank asks you to prove it), so instead of always multiplying by W one edge at a time, you can square: compute L^(2m) = L^(m) ⊙ L^(m), doubling how many edges are covered with every call. Starting from m=1, doubling reaches m ≥ n-1 after only ⌈lg(n-1)⌉ calls:

Fast exponentiation: to get x¹⁶ you do not multiply x sixteen times — you square four times (x → x² → x⁴ → x⁸ → x¹⁶). The same trick works on our "route budget": knowing the cheapest routes of at most m edges, combine the table with itself — "first half of a route, then second half" — and you know the cheapest routes of at most 2m edges.

Red = SLOW's one-step-at-a-time calls; green = FASTER's doubling calls (grey m = 1 is L⁽¹⁾ = W, given for free).

Small example first. For n = 5 the loop needs m to reach n−1 = 4: m = 1 → 2 → 4, so only 2 extend calls (SLOW would make 3). For n = 9 it is 3 calls instead of 7.

Θ(lg n) calls to a Θ(n³) routine give Θ(n³ lg n) — asymptotically better than slowAllPairsShortestPaths's Θ(n⁴) for large n. (Overshooting past exactly n-1 edges is harmless: δ stops changing once you reach n-1 edges.)

Two things people get wrong. (1) Squaring must combine L with L, not with W: L ⊙ W only adds one edge of budget, which is SLOW again. (2) The loop condition is m < n−1, and m may overshoot n−1 (n = 6 ends at m = 8): that is harmless because δ does not change once the budget reaches n−1.

Counting the calls: m takes the values 1, 2, 4, …, 2^t and the loop stops at the first 2^t ≥ n−1, so t = ⌈lg(n−1)⌉ calls (see the ladder above and the cost table in the last section). Each call is Θ(n³): total Θ(n³ lg n).

Repeated squaring is the same trick as fast exponentiation (compute x¹⁶ with 4 squarings instead of 15 multiplications) — here applied to the "min-plus" matrix product instead of ordinary multiplication. It only works because that product is associative; a non-associative "product" could not be doubled this way. Cost: Θ(n³ lg n).

The variable m counts edges (it is not an index), so while (m < n − 1) is exactly the loop condition above.

Input size → what is feasible: n ≤ 200 → ⌈lg 199⌉ = 8 calls × 8·10⁶ = 6.4·10⁷ steps is fine; n = 1000 → 10 calls × 10⁹ = 10¹⁰ is too slow, Floyd-Warshall needs 10⁹.

The maths as code. Θ(n³ lg n) versus Θ(n⁴) by counting calls: SLOW makes n−2, FASTER makes ⌈lg(n−1)⌉, each call costs n³.

The Floyd-Warshall algorithm

Floyd-Warshall asks a different question than the matrix-multiplication view: instead of growing the number of edges allowed, it grows the set of vertices allowed as intermediate stops. Define d_ij^(k) = the shortest i-to-j path weight using only vertices {0, …, k−1} as intermediate stops (the endpoints i, j don't count as "intermediate"). With k=0 no intermediates are allowed, so d_ij⁽⁰⁾ = w_ij (direct edge or ∞). Allowing one more vertex, k, asks one question: does routing through it ever help? (the stops recurrence):

d_ij^(k+1) = min( d_ij^(k), d_ik^(k) + d_kj^(k) )

and the matching predecessor update: keep the old predecessor if the direct route (without k) is still at least as good; otherwise the new predecessor is whatever k's own predecessor was on the k-to-j leg:

π_ij^(k+1) = π_ij^(k) if d_ij^(k) ≤ d_ik^(k) + d_kj^(k), else π_kj^(k)

floydWarshall(W)

Three nested loops (k, then i, then j), O(1) work each: Θ(n³) time. Only the current and previous D/Π matrices are ever needed at once, and you can even drop the copies and update a single n×n matrix in place — Θ(n²) space, the tightest of every algorithm in this lesson, and in practice among the fastest thanks to its tiny constant factor and simple loop structure.

Small example first. Triangle 0→1 (cost 2), 1→2 (cost 3), 0→2 (cost 7). With no stops d₀₂ = 7. When vertex 1 becomes allowed (round k = 1), the test asks "is 2 + 3 = 5 less than 7?" — yes, so d₀₂ becomes 5. Vertices 0 and 2 as stops change nothing. That single question, asked for every cell and every k, is the whole algorithm.

Loop invariant: before round k begins, d_ij already equals the shortest-path weight from i to j using only intermediate vertices from {0, …, k−1}, for every i, j. The round restores the invariant for {0, …, k} by asking exactly one question per cell: "does vertex k help?" After the last round, intermediates are allowed to be any vertex, so D = δ.

Check the diagonal of the final D. In a graph with no negative-weight cycle, every shortest path from a vertex to itself has weight exactly 0 (the empty path). If any d_ii < 0, that path loops through a negative-weight cycle back to i — the graph has one, and none of the reported distances that cycle can reach are trustworthy.

floydWarshall: Θ(n³) time in every case, Θ(n²) space, handles negative weights, and a negative diagonal entry at the end means a negative-weight cycle. The order of the loops matters: k must be the outermost loop — the invariant is about "stops allowed so far".

In Dart a null replaces "no predecessor" in Π, and vertex numbers are the 0-based indices themselves.

Input size → what is feasible: n ≤ 400 → n³ = 6.4·10⁷ steps, well under a second; n = 1000 → 10⁹ steps (seconds — roughly 1 to 10 s depending on the machine and implementation): use Johnson if the graph is sparse; n = 10⁴ → 10¹² steps and 10⁸ matrix cells, out of reach.

The maths as code. The stops recurrence as code (fwRounds), and the loop invariant "D^(k) uses only stops 0…k−1" checked against a brute-force path search.

The maths as code. The Θ(n³) bound: the innermost body runs exactly n³ times whatever the edges are (n = 10, 100, 1000).

The maths as code. Why one Θ(n²) matrix suffices: row k and column k cannot change during round k, because d_kk = 0.

Building the predecessor matrix Π inside floydWarshall

D is the price of the cheapest ticket; Π is the itinerary note. When the ticket from i to j gets cheaper because you now route through city k, you do not rewrite the whole itinerary. You only need "the last city before j" — and the k→j half of the trip already recorded exactly that: π_kj. Everything earlier in the itinerary can be recovered by asking Π again ("what was the stop before that one?").

Keep a matrix Π^(k) next to each D^(k), using the two update rules above. The pseudocode below is that idea written out:

Small example first. Tiny 3-depot graph: initially π₀₂⁽⁰⁾ = 0 (a direct edge 0→2 exists, so the vertex before 2 is 0) and d₀₂ = 7. At k = 1: through 1 costs d₀₁ + d₁₂ = 2 + 3 = 5 < 7, so d₀₂ := 5 and π₀₂ := π₁₂ = 1 ("the vertex before 2 on the 1→2 leg is 1"). Reading Π backward: 2 ← 1 ← 0, the route 0→1→2.

Each animation follows one chosen pair (i, j) through all n rounds while showing the whole D and Π matrices, so you can see the rule fire for every cell and, at every k, read the route straight out of row i of Π:

Cost: two O(1) assignments per cell instead of one, so still Θ(n³) time and Θ(n²) space. The Dart function below is the single-cell rule; the full floydWarshall panel earlier in this section applies it to every cell.

The classic slip is π_ij := π_ik. That is the vertex before k on the i→k leg, not the vertex before j. The new route ends "…→k→…→j", so the last hop into j belongs to the k→j leg: use π_kj. A second subtle point: the test is "≤" (ties keep the old route and its old predecessor), so equal-cost alternatives never make Π flip-flop.

Why Π stays correct (invariant): after round k, row i of Π^(k) describes a tree rooted at i whose tree paths are shortest paths that use only intermediate vertices from {0, …, k−1}. When d_ij improves through k, the new path is (tree path to k) + (tree path from k to j); its last edge is the last edge of the k→j tree path, which is π_kj. Everything before that edge is still described by the unchanged part of row i. With a negative-weight cycle the invariant fails and Π can contain a cycle — the trace in the next section shows what that does to path printing.

D says how much, Π says which way. Π costs only one extra assignment per cell, and row i of Π is a shortest-path tree rooted at i (the same idea as the single-source predecessor subgraph, once per source).

Input size → what is feasible: same size class as Floyd-Warshall (n ≤ 400): Π adds n² = 1.6·10⁵ entries and one more assignment per cell.

The maths as code. Row i of Π is a shortest-path tree: following π from j back to i adds up to exactly d_ij.

printAllPairsShortestPath(Π, i, j)

A treasure hunt where every clue says only "the previous stop was X". To read the route from start i to finish j you follow the clues backward from j until you reach i, then walk the route forward reading it out. The recursion does exactly that: the deepest call handles the start, and each call prints its own vertex after the call for the earlier part has returned, so vertices come out in travel order.

The procedure is the path-printing idea from the graph basics lesson: it reads row i of Π instead of a single-source π array.

Small example first. With Π from the tiny 3-depot graph (π₀₂ = 1, π₀₁ = 0): print(Π,0,2) sees 0 ≠ 2 and π₀₂ = 1 ≠ null, so it calls print(Π,0,1); that call sees π₀₁ = 0 and calls print(Π,0,0), which prints 0; back in the middle call it prints 1; back in the outer call it prints 2. Output: 0 1 2.

Running time: each recursive call moves to a different vertex of one shortest path, so a valid Π gives at most n calls — O(n), or exactly Θ(number of vertices on the path) — no matter how large the graph is. The Dart code has a recursive version and an iterative one (used in the question bank).

Three ways it goes wrong. (1) Printing j before the recursive call prints the route backwards. (2) Using the wrong row: the row is the source i (π_ij), not column i. (3) Feeding it a Π built from a graph with a negative-weight cycle: row i can contain a cycle and the recursion never reaches the base case (try the custom player with a negative cycle; our trace stops after n calls, real code would overflow the stack).

Why the recursion is correct: by the invariant of the previous section, the edges (π_ij, j) of row i form a shortest-path tree rooted at i. Walking from j toward the root along parent pointers therefore reaches i in at most n−1 steps, and each step's edge lies on a shortest i-to-j path (subpaths of shortest paths are shortest). Printing after the recursive call reverses "j → root" into "root → j".

printAllPairsShortestPath turns the n² parent pointers of Π into any of the n² actual routes in O(path length) time, without storing the routes themselves.

Input size → what is feasible: n ≤ 1000 with up to 10⁴ queries → at most 10⁷ steps, because each query costs one step per vertex of its route.

The maths as code. The O(n) bound: one recursive call per vertex of the route.

Transitive closure

Sometimes you don't care about weight at all — only "can you get from i to j at all?" That's the transitive closure G* = (V, E*), where (i,j) ∈ E* exactly when some path exists from i to j in G. You could run Floyd-Warshall with every edge weight set to 1 and check d_ij < ∞ — but a direct boolean version, replacing min/+ with OR/AND, avoids arithmetic entirely and can be implemented with fast bitwise operations on real hardware.

Let t_ij^(k) = 1 if a path from i to j exists using only intermediate vertices in {0,…,k−1}, else 0:

t_ij^(k+1) = t_ij^(k) ∨ ( t_ik^(k) ∧ t_kj^(k) )

transitiveClosure(n, edges)

Small example first. Edges 0→1 and 1→2 only. Initially t₀₂ = 0 (no direct edge). When vertex 1 becomes an allowed stop (k = 1): t₀₁ = 1 and t₁₂ = 1, so t₀₂ = 0 ∨ (1 ∧ 1) = 1 — 2 is reachable from 0 through 1.

Same three nested loops as Floyd-Warshall: Θ(n³) time, Θ(n²) space.

Initialise the diagonal to 1 (t_ii⁽⁰⁾ = 1: every vertex reaches itself by the empty path). Forgetting that breaks the recurrence for paths whose first or last stop is k itself. Also remember the matrix says "a path exists", not "an edge exists": the closure of a chain 0→1→2 has an extra 1 at (0,2).

Two alternatives worth knowing. (1) Run floydWarshall with every weight 1 and read "d_ij < ∞" — same Θ(n³) but slower arithmetic. (2) Pack each row into machine words and replace the inner j-loop by "if t[i][k] then row[i] |= row[k]": Θ(n³/w) word operations for word size w — the bitmask version in the question bank does exactly this.

transitiveClosure is Floyd-Warshall with the arithmetic stripped out — same invariant, same k-by-k growth of "which vertices may I pass through", just tracking a yes/no reachability bit instead of a numeric weight. Any graph algorithm built from min/+ in this pattern can be swapped to a different pair of operations (here ∨/∧) as long as they form a "closed semiring".

In Dart edges are pairs of 0-based indices, and true/false replace 1/0.

Input size → what is feasible: n ≤ 400 → n³ = 6.4·10⁷ boolean steps is fine; n ≤ 62 packed into 64-bit words → only n² = 3,844 word operations; n = 10⁴ → even n³/64 ≈ 1.6·10¹⁰ is heavy, condense strongly connected components first.

The maths as code. The two alternatives from the text: Floyd-Warshall with every weight 1 (read "d < ∞"), and bit-packed rows with the Θ(n³/w) word count.

Johnson's algorithm for sparse graphs

Floyd-Warshall's Θ(n³) doesn't care how many edges the graph actually has — even a nearly-empty graph costs the same as a complete one. For a sparse graph (few edges), running Dijkstra from every vertex would be much faster — if all the weights were nonnegative (Dijkstra's greedy proof breaks with negative weights). Johnson's trick: change every edge weight so they all become nonnegative, WITHOUT changing which paths are shortest.

The reweighting fact: pick any function h: V → ℝ and define ŵ(u,v) = w(u,v) + h(u) − h(v). For any path p = ⟨v₀, v₁, …, v_k⟩, the sum ŵ(p) = w(p) + h(v₀) − h(v_k) — every interior h term telescopes away, leaving only the two endpoints. Since every i-to-j path picks up the same +h(i) − h(j) adjustment, whichever path was shortest under w is still shortest under ŵ — reweighting cannot change the answer, only the numbers along the way. (For a cycle, v₀ = v_k, so ŵ(cycle) = w(cycle) exactly — reweighting cannot hide or create a negative cycle either.)

To get nonnegative ŵ, add a new vertex s with a 0-weight edge to every real vertex, forming G'. Run Bellman-Ford once from s: if it reports a negative-weight cycle, G has one too, and Johnson's stops right there. Otherwise set h(v) = δ(s,v). The triangle inequality for shortest paths, δ(s,v) ≤ δ(s,u) + w(u,v), rearranges to exactly ŵ(u,v) = w(u,v) + h(u) − h(v) ≥ 0 for every edge.

Reweighting on the graph: the h values and why every ŵ ≥ 0

Give every city an altitude h(v) and adjust every road's toll by the drop in altitude: ŵ = w + h(u) − h(v) (driving downhill makes the toll bigger, uphill smaller). Now choose "altitude = the cheapest cost to reach that city from a depot s". Arriving in v by any road can never be cheaper than the best known way to v — so no road ends up with a negative adjusted toll. And a whole trip from i to j always picks up the same adjustment h(i) − h(j), because the altitudes of all the cities in between cancel.

Small example first. In the 5-vertex graph used below, the edge 1→3 has weight −4 (negative!). Bellman-Ford from s gives h(1) = 0 and h(3) = −4, so ŵ(1,3) = −4 + 0 − (−4) = 0. The edge 0→3 (weight 3) has h(0) = 0 and h(3) = −4: ŵ(0,3) = 3 + 0 − (−4) = 7. The players below reweight every edge, one at a time, and show which inequality guarantees the result is never negative.

Common mistakes: (1) reweighting with an arbitrary h — any h keeps shortest paths unchanged, but only h(v) = δ(s,v) guarantees ŵ ≥ 0; (2) using the wrong sign: it is + h(u) − h(v) (tail minus head) on the edge and + h(v) − h(u) when undoing the shift on a result; (3) forgetting that s only exists to define h: s and its 0-edges are dropped before Dijkstra runs.

The nonnegativity proof in one line: for an edge (u,v), the walk "s → u by a cheapest route, then edge (u,v)" is a route to v, so the cheapest route to v is no more expensive: δ(s,v) ≤ δ(s,u) + w(u,v), i.e. h(v) ≤ h(u) + w(u,v), i.e. ŵ(u,v) = w(u,v) + h(u) − h(v) ≥ 0. Edges with ŵ = 0 are the "tight" ones that lie on a cheapest route from s.

Reweighting is a change of altitude, not of geography: negative edges disappear, every i→j route shifts by the same constant h(i) − h(j), so the winning route is unchanged and Dijkstra becomes legal.

The maths as code. The reweighting fact as code: path weights shift by h(start) − h(end) (interior terms telescope), cycles do not change, h = δ(s, v) makes every ŵ ≥ 0, and the un-reweighting formula.

Input size → what is feasible: reweighting costs O(E): E = 10⁶ edges is instant; the Bellman-Ford step costs O(VE), so V·E ≤ 10⁸ (for example V = E = 10⁴) is the practical limit.

johnson(n, edges)

One Bellman-Ford run costs O(VE). n Dijkstra runs on the reweighted graph cost O(V² lg V + VE) total with a Fibonacci heap (or O(VE lg V) with a binary heap). Either way, for a sparse graph (E = O(V)), this beats Floyd-Warshall's Θ(V³).

Where Johnson's implementations go wrong: running Dijkstra on the original weights (negative edges break its greedy proof); forgetting the final un-reweighting d = δ̂ + h(v) − h(u), which returns distances that are off by exactly the h difference; and not stopping when Bellman-Ford reports a negative cycle — with one present, h does not exist.

Correctness in one line: the reweighting fact says shortest paths under ŵ are the same paths as under w, so Dijkstra on (G, ŵ) finds the right paths; the final un-reweighting d(u,v) = δ̂(u,v) + h(v) − h(u) just undoes the telescoping adjustment to recover the true weight δ(u,v) under the original w.

Johnson = 1 Bellman-Ford (O(VE)) + reweight (O(E)) + V Dijkstras + V² un-reweightings. Total O(V² lg V + VE) with Fibonacci heaps — for sparse graphs (E = O(V)) that is roughly V² lg V, beating Floyd-Warshall's V³.

The new source s becomes index n (one past the last real vertex); every real vertex keeps its index.

Input size → what is feasible: V = 1000, E = 5000 (sparse) → about 6·10⁷ heap steps, fine, while Floyd-Warshall needs 10⁹; V = 200, E = 39,800 (dense) → Floyd-Warshall is simpler and faster.

Comparing the algorithms: running-time analysis

Choosing an algorithm is like choosing a delivery plan by counting truck trips: SLOW sends a truck n−2 times, FASTER sends it lg n times, Floyd-Warshall sends it once with a cleverer route, and Johnson trades trips for a sorting table (the heap). To compare fairly we count "basic steps" and look at the formula, not the vibes.

Small example first. With V = 10: one extend call is 10³ = 1,000 steps. SLOW makes 8 calls (8,000), FASTER ⌈lg 9⌉ = 4 calls (4,000), Floyd-Warshall 1,000. The cost table below computes these numbers live for any size and shows why the ranking flips between sparse and dense graphs:

Where each bound comes from (derivations, one line each):

Algorithm	Counting argument	Result
extendShortestPaths	3 nested loops (i, j, k), n iterations each, O(1) body	Θ(n³)
slowAllPairsShortestPaths	calls for m = 2 … n−1 → n−2 calls × Θ(n³)	Θ(n⁴)
fasterAllPairsShortestPaths	m doubles until ≥ n−1 → ⌈lg(n−1)⌉ calls × Θ(n³)	Θ(n³ lg n)
floydWarshall	loops k, i, j, n iterations each, O(1) body (no inner calls)	Θ(n³)
transitiveClosure	same three loops with ∨/∧	Θ(n³)
johnson	Bellman-Ford O(VE) + V × Dijkstra O(V lg V + E) (Fibonacci heap)	O(V² lg V + VE)

Big-O hides constants: Floyd-Warshall's inner loop is three array reads and a compare, so it often beats a "better" bound at moderate sizes, while Johnson's heap-based Dijkstra has a much heavier constant. The numbers above ignore constants entirely — near-ties are ties; measure before you commit.

Where the crossover is: Johnson wins when V·E·(lg V) (binary heap) is well below V³, i.e. roughly when E < V²/lg V. On graphs with E = Θ(V) the gap is a factor ~V / lg V; at E = Θ(V²) Johnson is about a factor lg V worse. Space: Floyd-Warshall and the two matrix methods need Θ(n²) for the answer matrix anyway; Johnson needs only O(V + E) beyond the output.

Rule of thumb: nonnegative weights and a huge sparse graph → Dijkstra from each source; negative weights and sparse → Johnson; dense or small → Floyd-Warshall; only reachability → transitive closure (bit-packed if you can).

The maths as code. The bounds V³ (Floyd-Warshall), V·E + V(V+E) lg V (Johnson, binary heap) and V² lg V + VE (Fibonacci heap) evaluated for the two sizes in the cost table.

Quiz

Interview questions

Cheat sheet

Algorithm	Time (best / average / worst)	Space	Negative weights?	Use when…
extendShortestPaths (1 call)	Θ(n³) in all cases	Θ(n²)	Yes (no negative cycle)	One "min-plus product" step; building block for the two below
slowAllPairsShortestPaths	Θ(n⁴) in all cases	Θ(n²) with two matrices (Θ(n³) if every L^(m) is kept)	Yes (no negative cycle)	Teaching the matrix-multiplication view; never in production
fasterAllPairsShortestPaths	Θ(n³ lg n) in all cases	Θ(n²) (two matrices, swapped)	Yes (no negative cycle)	Matrix-multiplication view with only ⌈lg(n−1)⌉ squarings
floydWarshall (with Π)	Θ(n³) in all cases	Θ(n²)	Yes; negative diagonal ⇒ negative cycle	Dense graphs, or any graph when Θ(n³) is affordable — simplest correct choice, smallest constant
printAllPairsShortestPath	Θ(k) for a path of k vertices; O(n) worst, Θ(1) when i = j or null	O(n) recursion depth	Needs a valid Π (no negative cycle)	Turning row i of Π into an actual route
transitiveClosure	Θ(n³) in all cases (Θ(n³/w) bit-packed)	Θ(n²) bits	N/A (reachability only)	"Can i reach j at all?" queries, ignoring weight
johnson	O(V² lg V + VE) Fibonacci heap; O(VE lg V) binary heap; early exit O(VE) when Bellman-Ford finds a negative cycle	O(V²) output + O(V+E)	Yes; the Bellman-Ford phase detects negative cycles up front	Sparse graphs (E = O(V)) — asymptotically beats Floyd-Warshall
Reweighting ŵ = w + h(u) − h(v)	O(E) after h is known	O(E)	Produces only ŵ ≥ 0 when h = δ(s,·)	Making Dijkstra legal on a graph with negative edges

"Commonly reported" company tags in the question bank reflect publicly shared interview experiences and are indicative, not verified lists.