One triple loop answers all-pairs reachability or shortest paths at once: for every possible middle vertex k, ask whether going through k beats what you had. With OR/AND it is transitive closure (who can reach whom); with min/plus it is shortest paths. Six lines, a 2-D table, and a lineage of four names.
THE TECHNIQUE try every vertex as a middle
Keep a table d[i][j]. For each vertex k in turn, update every pair: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) — is the path through k shorter? After all k, the table holds every shortest distance. (Swap min/+ for OR/AND and it is reachability.) Watch the matrix fill as k marches. live demo
HISTORY & CREDIT four discoverers for six lines
“Floyd-Warshall, 1962” — Roy published the same method in 1959, three years earlier, in French. cited
1956 · Stephen Kleene — the algebraic ancestor: converting a finite automaton to a regular expression is this same closure over an algebra. 1959 · Bernard Roy publishes the transitive-closure algorithm — the true first, overlooked because it was in French. 1962 · Stephen Warshall (transitive closure) and Robert Floyd (shortest paths, adapting Warshall) publish — both independently of Roy, though Floyd built on Warshall — the two names that stuck. the shape · O(n³) time, O(n²) space, and it handles negative edges (unlike Dijkstra) — just not negative cycles.
The same six lines are closure, shortest paths, and regex-from-automaton — one algorithm wearing three hats. Roy 1959 / Warshall & Floyd 1962
RECOMMEND FOR I-13 a 2-D table, flattened
The triple loop runs on a flattened matrix — and the all-pairs distances come out on the compiler:
Recommend:nothing new — the matrix is 2-D (PS-004), flattened to d[i*n+j], and the update is min + add (verified d[0][2]=4). The transitive-closure form is the bitwise variant (d = d | (d&d) per pair), which the integrated & | handle. One algorithm, both landed primitives. Note: Floyd-Warshall is the natural companion to Bellman-Ford (046, one source, negative edges) and Dijkstra (055, one source, non-negative) — the all-pairs corner of the same family.