Floyd-Warshall — All-Pairs Shortest Paths via DP

Why it matters

Floyd-Warshall is standard APSP for dense. Simple + reliable.

The architecture

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate k.

Triple nested loop.

How it works end to end

Path reconstruction: track predecessors.

Transitive closure: same algorithm with OR + AND.

Negative cycles: dist[i][i] < 0 for some i.