Floyd–Warshall Theory

Problem & Goal

Compute shortest path distances between all ordered pairs of vertices in a directed weighted graph (can include negative edges). Detect whether any negative cycle is reachable from a vertex.

Dynamic Programming Formulation

• State: dist_k[i][j] shortest distance from i to j using only intermediate vertices in {1..k}.
• Base: dist_0[i][j] = direct edge weight (∞ if none); dist_0[i][i] = 0.
• Transition: dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j])
• Optimization: Update in-place: treat matrix as holding dist_{k-1} then upgrade to dist_k.
• Cycle Detection: After loops, if dist[i][i] < 0 a negative cycle is reachable from i.

Pseudocode

1FLOYD-WARSHALL(dist, n):
2  for i in 1..n:
3    dist[i][i] = min(0, dist[i][i])  # allow 0 self
4  for k in 1..n:
5    for i in 1..n:
6      for j in 1..n:
7        if dist[i][k] + dist[k][j] < dist[i][j]:
8          dist[i][j] = dist[i][k] + dist[k][j]
9  # negative cycle detection
10  for v in 1..n:
11    if dist[v][v] < 0:
12      report "negative cycle reachable from v"

Complexity

Triple nested loops produce cubic time. Space dominated by distance (and optional successor) matrix. Works best for dense graphs (edge count near n^2).

Negative Cycles

If dist[i][i] < 0 after completion, then there exists a cycle of negative total weight reachable from i. Distances involving that cycle are not well-defined (can be driven arbitrarily low).

Path Reconstruction

Maintain a next[i][j] matrix: initialize to j if edge (i,j) exists. When improving dist[i][j] via k, set next[i][j] = next[i][k]. To reconstruct, iterate: i → next[i][j] until reaching j (or detect cycle if repeated).