Floyd-Warshall all-pairs shortest paths

Every pair's shortest distance, in one triple loop. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

The idea: allow intermediates one at a time

• Subproblem: shortest i→j using only nodes {0..k−1} as waypoints
• Grow k by one: either the old path, or i → k → j
• After every node is allowed, distances are final
• k MUST be the outermost loop (or it silently computes garbage)

Watch the matrix fill in

Cell (i,j) = best distance so far · dark = ∞ · teal diagonal = 0. Each frame switches on one intermediate node; improved cells flash orange.

Cost is blind to density

Floyd-Warshall = flat (ignores edge count). Dijkstra×V = rises with edges. Sparse: Dijkstra×V 5× faster. Dense: gap closes to 1.4×; compiled → FW wins.

Free extras

• Negative edges: handled (like Bellman-Ford)
• Negative cycle: dist[i][i] < 0 on the diagonal
• Transitive closure: same loop, or/and instead of min/plus (Warshall 1962)
• O(V²) memory ⇒ small/dense graphs only

Takeaway

Three lines, all pairs. Specialist for small/dense; wrong for huge sparse. Shortest-path thread done: BFS · Dijkstra · Bellman-Ford · Floyd-Warshall. Next: A* — a heuristic that steers toward a goal.