All-pairs shortest paths: one more stop-over each round

Old road atlases end with a table of driving distances between every pair of big cities. Fifty cities make 1,225 pairs. Running Dijkstra's algorithm once from each city would fill it, as long as no road has a negative length.

Floyd–Warshall fills the whole table in one go, with three loops and a single comparison, and it copes with negative lengths as long as no cycle adds up below zero. Its trick comes from dynamic programming: answer a smaller question first. Here the smaller question limits which cities a route may pass through, and each round allows one more.

distance matrix d

A V × V table: d[i][j] is the shortest distance found so far from i, the row, to j, the column.

stop-over

A node a route passes through between its two ends. A → C → D → B has two stop-overs, C and D.

round k

One pass over every pair (i, j) that also allows node k as a stop-over. There are V rounds, one per node.

negative cycle

A cycle whose weights add up to less than 0. Going round it once more always makes a route shorter, so a route that can take that detour has no shortest length.

next-hop matrix

next[i][j], the first step on the best path from i to j, kept beside d so the paths themselves can be read back.

Floyd–Warshall fills a dynamic programming table, built from the usual four decisions:

• State: after round k, d[i][j] is the length of the shortest path from i to j whose stop-overs are all k or nodes before it (in the visualiser, the nodes go in order A, B, C…).
• Base case: before any round no stop-over is allowed, so d holds the direct edges: the weight where there is one, 0 on the diagonal and ∞ everywhere else.
• Recurrence: the best path that may also use node k either avoids k, so d[i][j] stays, or passes through k once. Then it splits into i to k and k to j, neither of which stops over at k, so both are already in the table: d[i][j] = min(d[i][j], d[i][k] + d[k][j]).
• Fill order: k is the outer loop. Every pair finishes round k before any pair starts round k + 1.

Row k and column k hold the two halves of every route through k. The visualiser checks only the pairs that could improve, where i reaches k and k reaches j; the plain loops make 4 × 4 × 4 = 64 tests here.

Five towns, A to E, joined by roads that work both ways, so the matrix stays symmetric. Before each check, predict whether the route through k beats the d[i][j] already in the table.

By the end, A and E are 11 apart, along A → C → B → D → E. Round E checks 12 pairs and improves none: E's only road leads to D, so no route between two other towns gets shorter by visiting E.

Here is one round in code, with k = 1, on three nodes numbered 0 to 2. 99 stands for "no edge", since it is bigger than any real distance here. The full algorithm wraps these two loops in a third, over k = 0, 1, 2.

d = [[0, 4, 9], [6, 0, 2], [99, 1, 0]]
k = 1
for i in range(3):
    for j in range(3):
        if d[i][k] + d[k][j] < d[i][j]:
            d[i][j] = d[i][k] + d[k][j]
for row in d:
    print(str(row[0]) + ' ' + str(row[1]) + ' ' + str(row[2]))

The round tests row 1 and column 1 too, and never changes them. That holds in every round: d[i][k] could only become d[i][k] + d[k][k], and d[k][k] is 0. So every pair reads the same two halves whether other cells have been updated yet or not, which is why one matrix, overwritten in place, is enough.

Unlike Dijkstra, Floyd–Warshall settles nothing early: every pair is tested again each round, so negative edges are fine.

A negative cycle is different: a route round it comes back cheaper than it left, so the diagonal drops below 0.

The matrix gives lengths. For the routes, keep next[i][j] too: it starts as j wherever there is an edge, and whenever d[i][j] improves through k it becomes next[i][k], since the new route starts the way the best route to k does. To read a path, start at i and keep jumping to next[·][j] until you reach j. In Four cities, next[B][A] ends as C, next[C][A] as D and next[D][A] as A: B → C → D → A.

Swap min for or and + for and, and the same loops say whether j can be reached from i at all: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). That table is the graph's transitive closure.

Other algorithms fill the same table. Dijkstra's algorithm from every node costs O(V (V + E) log V) with a binary heap, if no edge is negative; Bellman–Ford from every node allows negative edges at O(V² E). Johnson's algorithm combines them: one Bellman–Ford run gives each node a number h, reweighting every edge u → v to w + h(u) − h(v) makes all weights non-negative without changing which paths are shortest, and Dijkstra then runs from every node.

• d starts as the direct edges, 0 on the diagonal and ∞ elsewhere. Round k allows k as a stop-over: d[i][j] = min(d[i][j], d[i][k] + d[k][j]).
• After round k, d[i][j] is the shortest path stopping over only at k and the nodes before it; after all V rounds it is the true distance.
• k must be the outer loop. One matrix is enough, because round k never changes row k or column k.
• Negative edges are fine; a negative cycle shows as a d[i][i] below 0. A next-hop matrix recovers the paths.
• Θ(V³) time whatever the edges, Θ(V²) memory: best for small or dense graphs. On large sparse ones, run Dijkstra from every node, or Johnson's algorithm if some edges are negative.
• Next: practise with Signal Spread Time, a one-source problem for Dijkstra (what would Floyd–Warshall cost with up to 500 nodes?), and try your own graph on the Floyd–Warshall and Bellman–Ford visualisers.