Floyd-Warshall solves shortest paths between every pair of vertices in a single O(|V|³) triple loop. Each outer step picks an intermediate vertex k and, for every pair (i, j), checks if routing through k is shorter than the current best dist[i][j]. Unlike Dijkstra, it tolerates negative edges (as long as there are no negative-weight cycles) — and it detects those cycles for you when a diagonal entry drops below zero. Watch the matrix fill and shrink step by step.
current row i=k / col j=k
updated (shorter via k)
considered
negative-cycle diagonal
Let d(k)[i][j] be the shortest path from i to j using only intermediate vertices from the set {1, 2, …, k}. Then either the shortest path already avoids vertex k — in which case d(k)[i][j] = d(k−1)[i][j] — or it passes through k exactly once, giving d(k)[i][j] = d(k−1)[i][k] + d(k−1)[k][j]. Take the minimum. The in-place implementation famously overwrites the same matrix as it goes because the row and column for the current k are stable within the pass: d[k][k] + d[k][k] can't improve anything else so long as d[k][k] = 0 (which stays true until a negative cycle appears).
A negative diagonal entry d[v][v] < 0 after the algorithm finishes is the ironclad signature of a negative-weight cycle reachable from v. Every APSP entry d[i][j] where i can reach some cycle vertex and that vertex can reach j is effectively −∞ — no finite shortest path exists.
| Floyd-Warshall | Dijkstra × |V| | Bellman-Ford × |V| | |
|---|---|---|---|
| Problem solved | all-pairs | all-pairs (via SSSP loop) | all-pairs (via SSSP loop) |
| Time complexity | O(|V|³) | O(|V|·(|V|+|E|) log |V|) | O(|V|²·|E|) |
| Negative edges | ✔ (no negative cycles) | ✘ | ✔ (no negative cycles) |
| Detects negative cycle | ✔ (diagonal < 0) | ✘ | ✔ |
| Best for | dense graphs, small |V| | sparse, non-negative | sparse, allows negative |