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

1. The All-Pairs Shortest Path Problem

Given a weighted directed graph G = (V, E) with n = |V| vertices and an edge-weight function w(u, v) (weights may be negative, as long as there is no negative-weight cycle), the all-pairs shortest path (APSP) problem asks for the shortest-path distance d(i, j) between every ordered pair of vertices (i, j).

The naïve approach — run a single-source algorithm like Bellman-Ford from every vertex — costs O(V² · E) with Bellman-Ford, since it must tolerate negative weights. Floyd-Warshall solves the same problem, negative weights included, in a flat O(V³) regardless of how many edges the graph has, which makes it the simplest correct choice for dense graphs.

2. Dynamic Programming Formulation

The trick, discovered independently by Robert Floyd and Stephen Warshall in 1962 (building on a related idea from Bernard Roy in 1959), is to think about paths not by their length but by which intermediate vertices they are allowed to pass through.

Define dist[k][i][j] as the length of the shortest path from i to j that uses only vertices from the set {1, 2, …, k} as intermediate stops (i and j themselves are always allowed as endpoints, whatever k is).

Because dist[k][·][·] only ever depends on dist[k-1][·][·], the entire 3-dimensional table can be collapsed into a single n×n matrix updated in place — this is the "matrix" behind the algorithm's compact implementation.

3. The Algorithm and Pseudocode

FLOYD-WARSHALL(W):  // W = n×n weight matrix, W[i][i] = 0, W[i][j] = ∞ if no edge
  dist = copy(W)
  next = n×n matrix, next[i][j] = j if edge (i,j) exists else null   // for path reconstruction

  for k = 1 to n:            // intermediate vertex allowed
    for i = 1 to n:
      for j = 1 to n:
        if dist[i][k] + dist[k][j] < dist[i][j]:
          dist[i][j] = dist[i][k] + dist[k][j]
          next[i][j] = next[i][k]     // route through k

  return dist, next

The whole algorithm is exactly three nested loops with a single comparison-and-update inside — no priority queue, no recursion, no auxiliary data structure. This simplicity is a large part of why it remains the standard textbook choice for teaching dynamic programming on graphs.

4. Correctness: Induction on Intermediate Vertices

The proof is a clean induction on k, the size of the allowed intermediate-vertex set:

• Base case (k = 0): With no intermediate vertices allowed, the only valid "paths" are direct edges or staying put, which is exactly the initial weight matrix W.
• Inductive step: Assume dist[k-1][i][j] is correctly the shortest {1..k-1}-restricted path for all i, j. Any shortest {1..k}-restricted i-j path either avoids k entirely (cost = dist[k-1][i][j]) or visits k. If it visits k, since a shortest path never visits the same vertex twice, it visits k exactly once, splitting into an i→k segment and a k→j segment, each of which is itself a shortest {1..k-1}-restricted path (otherwise you could substitute a shorter sub-path and improve the whole path, a standard "optimal substructure" argument). So its cost is exactly dist[k-1][i][k] + dist[k-1][k][j].
• Taking the minimum of these two cases gives exactly the recurrence used in the algorithm — hence dist[k][i][j] is correctly maintained at every step, and dist[n][i][j] is the true unrestricted shortest-path distance.

5. Complexity

Because the runtime is independent of the number of edges, Floyd-Warshall is at its best on dense graphs (E close to V²), where it matches or beats running Dijkstra V times. On sparse graphs, running a heap-based Dijkstra from every source, or the specialised Johnson's algorithm, is asymptotically faster — see the comparison table at the end.

6. Negative-Cycle Detection

Unlike Dijkstra, Floyd-Warshall handles negative edge weights gracefully — as long as the graph has no negative-weight cycle (a cycle whose total weight sums to less than zero, which would make "shortest path" undefined, since you could loop around it forever to decrease the total cost indefinitely).

This built-in diagnostic is one reason Floyd-Warshall remains popular even when a graph is sparse enough that Johnson's algorithm would be faster: the negative-cycle check comes essentially for free, whereas Bellman-Ford-based approaches need an explicit extra relaxation pass.

7. Path Reconstruction

The distance matrix alone doesn't tell you which vertices a shortest path visits. The standard fix is to maintain a parallel next[i][j] matrix (as shown in the pseudocode above), recording "the next vertex to go to on the shortest path from i to j":

RECONSTRUCT-PATH(next, i, j):
  if next[i][j] == null: return []       // no path exists
  path = [i]
  while i != j:
    i = next[i][j]
    path.push(i)
  return path

Each update next[i][j] = next[i][k] in the main loop simply says "if it's now faster to route i→j via k, then the first step out of i should be whatever the first step out of i towards k already was" — a small but essential detail that many naive implementations forget.

8. Floyd-Warshall vs Repeated Dijkstra vs Johnson's Algorithm

Johnson's algorithm gets the best of both worlds on sparse graphs: it runs a single Bellman-Ford pass to compute vertex potentials that re-weight every edge to be non-negative without changing which paths are shortest, then runs Dijkstra from every vertex on the reweighted graph. For dense graphs (E ≈ V²) the V·E log V term of Johnson's approaches V³ log V anyway, so plain Floyd-Warshall's O(V³) — with no reweighting overhead and much simpler code — usually wins in practice up to a few hundred vertices, which is why it remains the default choice taught first and used most often for moderate-sized graphs like road networks, game maps, and small-to-medium infrastructure topologies.