Floyd-Warshall Algorithm: All-Pairs Shortest Paths in O(V³)

Paths as sets of allowed intermediate vertices

Given a weighted directed graph with n = |V| vertices, the all-pairs shortest path problem asks for the distance d(i, j) between every pair. Robert Floyd and Stephen Warshall, in 1962, found the trick: think about paths not by length but by which intermediate vertices they are allowed to pass through. Define dist[k][i][j] as the shortest i→j path using only vertices {1, …, k} as intermediate stops.

dist[0][i][j] = w(i,j) if edge exists, 0 if i=j, else ∞

dist[k][i][j] = min( dist[k-1][i][j],
                      dist[k-1][i][k] + dist[k-1][k][j] )

Answer: dist[n][i][j] for every pair

A path using {1..k} either never touches vertex k (same cost as before) or passes through it exactly once, splitting into an i→k and a k→j segment. Because dist[k] only depends on dist[k−1], the whole 3D table collapses into one n×n matrix updated in place — three nested loops, no priority queue, no recursion.

live demo · the distance matrix tightening as pivot k advances● LIVE

Correctness, complexity, and the loop-order trap

The proof is a clean induction on k: assuming dist[k−1] is correct for all i, j, any shortest {1..k}-restricted path either avoids k (same cost) or visits it exactly once — an optimal-substructure argument that makes the recurrence exact. The algorithm runs in O(V³) time and O(V²) space regardless of edge count, which makes it the best choice on dense graphs where it matches or beats running Dijkstra V times. The k-loop must be outermost — the recurrence needs dist[k−1] fully finalised before k is used as a new intermediate stop, and swapping the loop order silently breaks correctness.

Negative cycles come almost for free

Unlike Dijkstra, Floyd-Warshall handles negative edge weights gracefully, as long as no cycle sums to less than zero. After running the algorithm, check the diagonal: dist[i][i] starts at 0 and can only turn negative if some cycle through i has negative total weight — exactly the definition of a negative cycle. This diagnostic is a large part of why Floyd-Warshall remains popular even on graphs where a faster method exists: Johnson's algorithm (Bellman-Ford once to reweight edges non-negative, then Dijkstra from every vertex) beats Floyd-Warshall's O(V³) on sparse graphs with negative weights, at O(V²log V + VE), but needs an explicit extra pass for the same check.

Frequently asked questions

Why must the intermediate-vertex loop k be outermost?

The recurrence relies on dist[k-1] being fully finalised before it is used as an intermediate stop for k. Swapping the loop order silently produces incorrect results that may still look plausible on small test graphs, because the invariant that k-1-restricted distances are already optimal is broken.

How does Floyd-Warshall detect negative-weight cycles?

After running the algorithm, check the diagonal of the distance matrix: dist[i][i] starts at 0 for every vertex and can only become negative if some cycle through i has negative total weight. This diagnostic comes essentially for free, unlike Bellman-Ford-based approaches which need an explicit extra relaxation pass.

When should I use Floyd-Warshall instead of running Dijkstra from every vertex?

Floyd-Warshall runs in O(V³) regardless of edge count, which makes it the simplest correct choice for dense graphs (E close to V²) and for graphs with negative weights, where Dijkstra cannot be used at all. On sparse graphs with only non-negative weights, running a heap-based Dijkstra from every source is asymptotically faster.

Try it live

Everything above runs in your browser — open Floyd-Warshall and step through the algorithm, watching the distance matrix tighten as the pivot k advances across every vertex.

▶ Open Floyd-Warshall simulation