Floyd-Warshall
All-pairs shortest paths-algoritm — räknar kortaste väg mellan varje par av noder. Robert Floyd / Stephen Warshall (1962).
Genial DP-formulering: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) för varje mellanliggande nod k. Tre nested loops, 8 rader kod. Tidskomplexitet: O(V³) — opraktisk för stora grafer men perfekt för <200 noder.
Driver routing-tabeller i små nätverk, transitive closure, "kortaste handshake mellan två personer i en social graf". Hanterar negativa vikter (men inte negativa cykler). Konkurrent: Johnson's algorithm (V·E·logV, bättre för sparse grafer).