FLOYD-WARSHALL all pairs at once — can I get from i to j through k?
Floyd-Warshall finds the shortest path between every pair of nodes at once, with three nested loops and one beautiful idea: consider the intermediate nodes one at a time. For each possible waypoint k, ask of every pair (i, j): is going i→k→j shorter than the best i→j so far? After allowing all k as waypoints, the matrix holds every shortest distance. It is dynamic programming on the adjacency matrix, O(V³), and its transitive-closure cousin answers reachability the same way. On the weighted graph, the shortest distance from 0 to 4 is 7.
THE TECHNIQUE for each waypoint k: dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
The demo runs Floyd-Warshall on the weighted graph — the all-pairs shortest distance from 0 to 4 is 7: live demo
HISTORY & CREDIT Floyd & Warshall · 1962
“All-pairs shortest paths need V separate runs.” — Floyd-Warshall does it in one triple loop, adding waypoints one at a time. cited
the waypoint · for each k, test dist[i][k]+dist[k][j] against dist[i][j] — allow k as a stop. the DP · after all k, every shortest distance is found — O(V³), on the adjacency matrix. 1962 · Floyd & Warshall (Roy, 1959) — all-pairs shortest paths and transitive closure.
Every pair’s shortest route found by admitting one waypoint at a time — dynamic programming on a matrix. all-pairs
RECOMMEND FOR I-13 the all-pairs distances, on the compiler
On the canonical compiler, Floyd-Warshall gives shortest distance 7 from node 0 to node 4 (and 3 from 0 to 1):
$ i13 run nw_floydwarshall.i13 # DP over intermediate k
RUN OK · 7172 step(s) · peak stack 26 · call depth 36
d[0][4] = 7 d[0][1] = 3
ok = 1
Recommend as a NULL — dynamic programming, a computed matrix. Floyd-Warshall computes the all-pairs shortest-distance matrix — forall-pinned by the graph (B39) — by DP over waypoints (B40). No new invariant. NULL — every shortest path at once, waypoint by waypoint.