Floyd-Warshall: All-Pairs Shortest Paths

The Floyd-Warshall algorithm computes the shortest path between every pair of vertices in a weighted graph in a single run, using dynamic programming instead of repeatedly solving a single-source shortest-path problem. It handles negative edge weights (as long as there’s no negative cycle) and runs in O(V³) time and O(V²) space, where V is the number of vertices.

The problem it solves

Algorithms like Dijkstra’s and Bellman-Ford find shortest paths from a single source vertex to every other vertex. If you need shortest paths between every pair of vertices, the naive approach is to run one of those algorithms once per vertex. Floyd-Warshall instead builds the full distance matrix directly, considering one candidate “intermediate” vertex at a time across the whole graph.

The core idea: intermediate vertices

Floyd-Warshall starts from the graph’s direct edges — the distance matrix initialized so that dist[i][j] is the weight of the edge from i to j if one exists, zero if i == j, and infinity otherwise. It then asks, for each vertex k in turn: does routing through k shorten any existing path?

The recurrence is:

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

For every pair (i, j), this checks whether going from i to k and then k to j is shorter than the best path found so far. Run that check for every (i, j) pair while allowing k = 1, then again allowing k up to 2, and so on up through every vertex. By the time k has covered every vertex, dist[i][j] holds the true shortest path from i to j, allowed to route through any vertex in the graph.

Walking through the algorithm

for k in 1..n:
  for i in 1..n:
    for j in 1..n:
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

That triple-nested loop is the entire algorithm — no priority queue, no visited set, no per-source restart. Each pass over k adds one more vertex to the set of allowed intermediate stops, and the distance matrix only ever improves, never gets worse, because dist[i][j] starts as an upper bound (direct edge or infinity) and the recurrence only replaces it with something smaller.

Why it works

The correctness argument rests on optimal substructure: the shortest path from i to j that’s allowed to pass through vertices {1, ..., k} either doesn’t use vertex k at all (in which case it’s the same as the best path using {1, ..., k-1}), or it does use k, in which case it’s the best path from i to k plus the best path from k to j, both restricted to intermediate vertices {1, ..., k-1}. Since the loop processes k in increasing order and always has the correct restricted-path values from the previous iteration, each step’s answer is provably correct before moving on.

Negative edges and negative cycles

Floyd-Warshall handles negative edge weights correctly, which single-source algorithms like Dijkstra cannot (Dijkstra’s greedy vertex selection breaks down once a later, cheaper path can undercut an already-finalized one). Floyd-Warshall doesn’t have that problem because it doesn’t finalize vertices greedily — it revisits every pair on every pass.

It also detects negative cycles for free: after the algorithm finishes, check the diagonal of the distance matrix. If any dist[i][i] is negative, there’s a negative-weight cycle reachable from and back to vertex i, and the “shortest path” values touched by that cycle are meaningless (a cycle you can loop forever to keep lowering the cost).

Floyd-Warshall vs running Dijkstra from every vertex

	Floyd-Warshall	Dijkstra from every source
Time complexity	O(V³)	O(V · (E log V)) with a binary heap
Negative edges	Handled	Not supported
Negative cycle detection	Built in (check the diagonal)	Not applicable
Best on	Dense graphs, or when V is small	Sparse graphs, where E is much smaller than V²
Implementation	A few lines, no data structures needed	Needs a priority queue per run

On a dense graph, where E approaches V², the two approaches land in similar territory, but Floyd-Warshall’s simplicity — no priority queue, no per-source bookkeeping — makes it the more practical choice. On a sparse graph, running Dijkstra V times is asymptotically faster, since its cost scales with edges rather than the cube of vertices.

Where it shows up

Floyd-Warshall is a natural fit whenever you need a complete distance (or reachability) matrix rather than a single route: precomputing routing tables in small networks, computing the transitive closure of a graph (which vertices can reach which others at all, by treating edge weights as 1), and pathfinding on small, dense grids in games where every-pair distances get queried repeatedly. Its dynamic-programming structure is a good complement to reading about greedy algorithms and dynamic programming more broadly, and to graph traversal with BFS and DFS as the more basic building block those shortest-path algorithms build on. For a sense of why O(V³) is the complexity to expect from this style of triple-nested recurrence, see what Big O notation actually measures, and the master theorem for how divide-and-conquer algorithms get their own complexity bounds by comparison.

The takeaway

Floyd-Warshall fills in the full all-pairs shortest-path matrix by asking, for every candidate intermediate vertex in turn, whether routing through it beats the best path found so far. The triple-nested loop runs in O(V³) time, handles negative edges, and detects negative cycles by checking the matrix diagonal afterward — trading the asymptotic edge that per-source Dijkstra has on sparse graphs for simplicity and correctness guarantees that hold even when edge weights go negative.