All-Pairs Shortest Paths
Instead of running a single-source search from every vertex, Floyd-Warshall keeps one matrix of best known distances and improves it in rounds. Round k allows k as a stopover: for every pair, if the distance to k plus the distance from k beats the current entry, the entry is replaced. After every vertex has had its round, each entry is a true shortest distance, because any shortest path is built from stopovers that were each admitted at some point. The whole thing is three nested loops over the matrix.
Row i, column j: the shortest known distance from i to j, starting from the edges alone (∞ where there is no edge, 0 on the diagonal). Each round admits one more vertex k as a stopover and asks every pair whether going through k is shorter.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.
(1, 1) is 0; via 0 it would be 8 + 3. Update?
Answer: No, keep 0. 11 is not below 0, so nothing changes.
(1, 3) is ∞; via 0 it would be 8 + 7. Update?
Answer: Yes, to 15. 15 < ∞, so the stopover wins.
(2, 1) is ∞; via 0 it would be 5 + 3. Update?
Answer: Yes, to 8. 8 < ∞, so the stopover wins.
(3, 1) is ∞; via 0 it would be 2 + 3. Update?
Answer: Yes, to 5. 5 < ∞, so the stopover wins.
(0, 0) is 0; via 1 it would be 3 + 8. Update?
Answer: No, keep 0. 11 is not below 0, so nothing changes.
(0, 2) is ∞; via 1 it would be 3 + 2. Update?
Answer: Yes, to 5. 5 < ∞, so the stopover wins.
(3, 2) is ∞; via 1 it would be 5 + 2. Update?
Answer: Yes, to 7. 7 < ∞, so the stopover wins.
(0, 0) is 0; via 2 it would be 5 + 5. Update?
Answer: No, keep 0. 10 is not below 0, so nothing changes.
(0, 3) is 7; via 2 it would be 5 + 1. Update?
Answer: Yes, to 6. 6 < 7, so the stopover wins.
(1, 0) is 8; via 2 it would be 2 + 5. Update?
Answer: Yes, to 7. 7 < 8, so the stopover wins.
(1, 3) is 15; via 2 it would be 2 + 1. Update?
Answer: Yes, to 3. 3 < 15, so the stopover wins.
(0, 0) is 0; via 3 it would be 6 + 2. Update?
Answer: No, keep 0. 8 is not below 0, so nothing changes.
(1, 0) is 7; via 3 it would be 3 + 2. Update?
Answer: Yes, to 5. 5 < 7, so the stopover wins.
(2, 0) is 5; via 3 it would be 1 + 2. Update?
Answer: Yes, to 3. 3 < 5, so the stopover wins.
(2, 1) is 8; via 3 it would be 1 + 5. Update?
Answer: Yes, to 6. 6 < 8, so the stopover wins.
How it runs, step by step
Row i, column j: the shortest known distance from i to j, starting from the edges alone (∞ where there is no edge, 0 on the diagonal). Each round admits one more vertex k as a stopover and asks every pair whether going through k is shorter.
Distance matrix for 4 vertices from 7 edges.
Round k = 0: paths may now pass through 0. Row 0 holds the distances out of 0 and column 0 the distances into it, so a candidate for (i, j) is dist[i][0] + dist[0][j].
Round 0. Row and column 0 are the stopover distances.
(1, 1): via 0 costs dist[1][0] + dist[0][1] = 8 + 3 = 11, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
1 to 1 keeps 0.
(1, 3): via 0 costs dist[1][0] + dist[0][3] = 8 + 7 = 15, against ∞ so far. Shorter, so dist[1][3] becomes 15.
1 to 3 improves to 15 via 0.
(2, 1): via 0 costs dist[2][0] + dist[0][1] = 5 + 3 = 8, against ∞ so far. Shorter, so dist[2][1] becomes 8.
2 to 1 improves to 8 via 0.
(3, 1): via 0 costs dist[3][0] + dist[0][1] = 2 + 3 = 5, against ∞ so far. Shorter, so dist[3][1] becomes 5.
3 to 1 improves to 5 via 0.
Round k = 1: paths may now pass through 1. Row 1 holds the distances out of 1 and column 1 the distances into it, so a candidate for (i, j) is dist[i][1] + dist[1][j].
Round 1. Row and column 1 are the stopover distances.
(0, 0): via 1 costs dist[0][1] + dist[1][0] = 3 + 8 = 11, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
0 to 0 keeps 0.
(0, 2): via 1 costs dist[0][1] + dist[1][2] = 3 + 2 = 5, against ∞ so far. Shorter, so dist[0][2] becomes 5.
0 to 2 improves to 5 via 1.
(3, 2): via 1 costs dist[3][1] + dist[1][2] = 5 + 2 = 7, against ∞ so far. Shorter, so dist[3][2] becomes 7.
3 to 2 improves to 7 via 1.
Round k = 2: paths may now pass through 2. Row 2 holds the distances out of 2 and column 2 the distances into it, so a candidate for (i, j) is dist[i][2] + dist[2][j].
Round 2. Row and column 2 are the stopover distances.
(0, 0): via 2 costs dist[0][2] + dist[2][0] = 5 + 5 = 10, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
0 to 0 keeps 0.
(0, 3): via 2 costs dist[0][2] + dist[2][3] = 5 + 1 = 6, against 7 so far. Shorter, so dist[0][3] becomes 6.
0 to 3 improves to 6 via 2.
(1, 0): via 2 costs dist[1][2] + dist[2][0] = 2 + 5 = 7, against 8 so far. Shorter, so dist[1][0] becomes 7.
1 to 0 improves to 7 via 2.
(1, 3): via 2 costs dist[1][2] + dist[2][3] = 2 + 1 = 3, against 15 so far. Shorter, so dist[1][3] becomes 3.
1 to 3 improves to 3 via 2.
Round k = 3: paths may now pass through 3. Row 3 holds the distances out of 3 and column 3 the distances into it, so a candidate for (i, j) is dist[i][3] + dist[3][j].
Round 3. Row and column 3 are the stopover distances.
(0, 0): via 3 costs dist[0][3] + dist[3][0] = 6 + 2 = 8, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
0 to 0 keeps 0.
(1, 0): via 3 costs dist[1][3] + dist[3][0] = 3 + 2 = 5, against 7 so far. Shorter, so dist[1][0] becomes 5.
1 to 0 improves to 5 via 3.
(2, 0): via 3 costs dist[2][3] + dist[3][0] = 1 + 2 = 3, against 5 so far. Shorter, so dist[2][0] becomes 3.
2 to 0 improves to 3 via 3.
(2, 1): via 3 costs dist[2][3] + dist[3][1] = 1 + 5 = 6, against 8 so far. Shorter, so dist[2][1] becomes 6.
2 to 1 improves to 6 via 3.
Every entry is now the shortest distance, 11 updates in all. Three nested loops over 4 vertices: O(n cubed), and negative edges are fine as long as there is no negative cycle.
All pairs done with 11 updates.
Remember
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), for every pair, one k at a time.
- Row k and column k are the stopover distances for round k; they never change during that round.
- A negative diagonal entry after the last round means a negative cycle.
Topics covered
Related
Where this is used
Developer toolsSciPy and NetworkX
scipy.sparse.csgraph.floyd_warshall and networkx.floyd_warshall_numpy return the whole matrix from one call, and the same SciPy module also ships dijkstra and johnson. Negative weights rule out dijkstra and leave floyd_warshall and johnson; density decides between those two. Floyd-Warshall is the one you pick when the graph is dense and the vertex count is in the hundreds: there is no priority queue and no per-source setup, and the inner loop is a straight walk over contiguous memory, so the n^3 carries a very small constant. On a sparse graph johnson wins, and on a sparse graph with no negative weights dijkstra from every source wins, which is why the library keeps all three.
CompilersReachability matrices in static analysis
Swap min for OR and plus for AND and the identical triple loop becomes Warshall's transitive closure: which function can reach which, which module depends on which, which definition can flow to which use. Because row k is fixed for the whole round, the inner j loop collapses into a row operation: `if (reach[i][k]) reach[i] |= reach[k]`, a bitwise OR of entire rows, so one machine word settles 64 pairs at a time. That bit-parallel form is why closure over a dense dependency graph is often faster as a matrix than as a traversal from every node.
SchedulingSchedules that have to stay consistent
The Simple Temporal Problem writes every timing constraint as t_j - t_i <= w, which is exactly a weighted edge, so a schedule is a graph. Running Floyd-Warshall over it produces the minimal network: the tightest gap that must hold between every pair of events, including pairs nobody wrote a constraint for, which is what lets a planner answer 'how late can this step start' directly. An impossible set of constraints shows up as a negative diagonal entry, so the feasibility check comes for free with the propagation.
OperationsDistance matrices for route optimisation
A vehicle routing solver such as Google OR-Tools never walks the road graph: you hand it a cost for every pair of stops, because it reorders those stops millions of times and each lookup has to be O(1). Building that table means collapsing the underlying graph into a complete graph over the stops alone, which is an all-pairs shortest path problem. For a warehouse aisle map or a few dozen sites with a dense travel-time table, one Floyd-Warshall pass fills it; on a country-sized road network you run Dijkstra from each stop instead.
Why it works this way
Why k has to be the outermost loop
The invariant is that after round k, every entry is the best path that uses only vertices 0..k as stopovers, and that induction only holds if one k is finished across the whole matrix before the next one starts. Move k inside and the loop still only ever writes lengths of real paths, so the numbers look plausible and small examples often come out right, but longer paths are missed and the matrix is silently not minimal. It is the most common Floyd-Warshall bug, and it does not crash or warn.
Where did the third dimension of the DP go?
The honest recurrence has one layer per round: d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]), which looks like it needs two matrices and a copy between rounds. It does not, because routing a path to k through k itself gains nothing while d[k][k] is 0, so d[k][i][k] equals d[k-1][i][k] and d[k][k][j] equals d[k-1][k][j]. The two entries the update reads are exactly the two that cannot move during the round, so reading a half-updated matrix gives the same answer as reading a clean one.
Infinity that overflows into a short path
If you spell 'no edge' as Int.MAX_VALUE, then dist[i][k] + dist[k][j] overflows: Int.MAX_VALUE plus a real weight wraps to about -2 billion, and Int.MAX_VALUE twice wraps to -2. Either way the sum comes out negative, the comparison passes, and a pair with no route at all is recorded as cheaper than any real path. Later rounds then route through that fake entry and the damage spreads. Either guard the update with a check that both halves are finite, or pick a sentinel such as 1_000_000_000 that can be added to itself without leaving Int range.
The matrix gives you lengths, not routes
Distances alone do not say which way to go. You can recover a route afterwards by looking for a neighbour v of i where weight(i, v) + dist[v][j] equals dist[i][j], but that is a scan over the edges for every hop of every query. The usual fix is a second n by n matrix next[i][j], set to j for each direct edge and updated to next[i][k] whenever the min is taken; a route is then a walk down that matrix and costs nothing at query time.