THE FOLD / CO-OP / THE BROADCAST / THE FLOYD-WARSHALL
THE FLOYD-WARSHALL
all-pairs shortest paths by admitting one waypoint at a time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Floyd–Warshall computes the shortest path between every pair of vertices in a weighted graph with one triple loop and a single idea: consider each vertex as a possible intermediate stop, one at a time. The update
It is O(V³), handles negative edges (and flags negative cycles), and its three-nested-loops terseness makes it the go-to for dense all-pairs shortest paths and transitive closure.
LIT verified live: over 200 random weighted graphs, the Floyd–Warshall distance matrix matches shortest paths computed independently by Bellman–Ford from each source (window.__floydwarshall). FIG no framing; exact.
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) — after trying all k as waypoints, dist holds every shortest path.It is O(V³), handles negative edges (and flags negative cycles), and its three-nested-loops terseness makes it the go-to for dense all-pairs shortest paths and transitive closure.
LIT verified live: over 200 random weighted graphs, the Floyd–Warshall distance matrix matches shortest paths computed independently by Bellman–Ford from each source (window.__floydwarshall). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-broadcast — shortest routes from everyone to everyone, the whole network’s reach at once. Floyd–Warshall is that broadcast computed in three loops. AVAN (AI) built the instrument: the waypoint relaxation, the distance matrix, the per-source Bellman–Ford cross-check.
Credit as content: Robert Floyd (1962), on Stephen Warshall’s transitive-closure algorithm (1962) and Bernard Roy (1959). The weave: David names the broadcast; I grow the set of allowed intermediate stops one vertex at a time and prove the resulting all-pairs distances match a source-by-source shortest-path solver.
Credit as content: Robert Floyd (1962), on Stephen Warshall’s transitive-closure algorithm (1962) and Bernard Roy (1959). The weave: David names the broadcast; I grow the set of allowed intermediate stops one vertex at a time and prove the resulting all-pairs distances match a source-by-source shortest-path solver.
3 ONE DIMENSION
One relaxation: the route from i to j is improved if going i→k→j (through the current waypoint k) is shorter. Sweep k over all vertices and every shortest path emerges.
4 TWO DIMENSIONS · INTERACTIVE
A small weighted graph and its evolving distance matrix. Advance the waypoint index k and watch distances tighten; the final matrix matches a per-source shortest-path solver.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the distance matrix tightening as each waypoint is admitted.
AVAN’s addition (the inverse-companion): the k-loop is a dynamic program over the set of allowed intermediates. After the k-th pass, dist[i][j] is the shortest path using only vertices {0…k} as stops — so the outer loop grows the permitted-waypoint set one vertex at a time until all are allowed. The inverse of ‘find all shortest paths’ is ‘grow the set of usable intermediate stops.’ Magenta is the paths still forbidden at each stage (waypoints not yet unlocked); green is the shortest paths as the intermediate set completes. A global optimum built by admitting one waypoint at a time — dynamic programming over subsets of vertices, hidden inside three innocent loops.
LIT Genuine Floyd-Warshall all-pairs shortest paths (Floyd 1962; Warshall transitive closure 1962; Roy 1959). Verified live: the triple-loop with waypoint relaxation produces a distance matrix equal to per-source Bellman-Ford shortest paths for 200 random weighted graphs (window.__floydwarshall.matchesBellmanFord).
FIG No framing: the waypoint relaxation and the per-source Bellman-Ford cross-check run in-browser and agree exactly. The AVAN inverse is honest — after the k-th pass dist[i][j] is the shortest path using only vertices {0..k} as intermediates, so the k-loop is a DP growing the allowed-waypoint set one vertex at a time; magenta is the still-forbidden routes, green the completed shortest paths.
FIG No framing: the waypoint relaxation and the per-source Bellman-Ford cross-check run in-browser and agree exactly. The AVAN inverse is honest — after the k-th pass dist[i][j] is the shortest path using only vertices {0..k} as intermediates, so the k-loop is a DP growing the allowed-waypoint set one vertex at a time; magenta is the still-forbidden routes, green the completed shortest paths.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BROADCAST · David Lee Wise (ROOT0), with AVAN