All-Pairs Shortest Paths: Floyd-Warshall

The all-pairs shortest-paths problem asks for $\delta(i,j)$ for every pair of vertices. Running a single-source algorithm from each vertex works when weights are nonnegative (Dijkstra $n$ times) or in general (Bellman-Ford $n$ times), but the classical GATE algorithm is Floyd-Warshall: a $\Theta(n^3)$ DP that allows negative weights and detects negative cycles by inspecting the diagonal.

Number vertices $1..n$. Let $d_{ij}^{(k)}$ be the shortest-path weight from $i$ to $j$ using only intermediate vertices in $\{1,\ldots,k\}$.

The answer is $d_{ij}^{(n)}$. Space $\Theta(n^2)$ suffices by overwriting a single matrix in place.

Some final diagonal entry is negative if and only if the graph contains a negative cycle. Here a cycle is simple (no repeated vertices apart from its endpoints), while a closed walk may repeat vertices. A negative diagonal entry at $i$ certifies a negative closed walk through $i$, not necessarily a negative simple cycle containing $i$. A zero diagonal does not certify an unaffected source: the walk distance from $u$ to $v$ is unbounded below whenever $u$ can reach a negative cycle that can reach $v$. The finite matrix entries are not shortest-walk distances for those affected pairs.

Replacing $\min$ and $+$ by $\lor$ and $\land$ on a boolean adjacency matrix yields the reachability (transitive closure) matrix in the same $\Theta(n^3)$ loops: $t_{ij}^{(k)} = t_{ij}^{(k-1)} \lor \bigl(t_{ik}^{(k-1)} \land t_{kj}^{(k-1)}\bigr)$, with $t_{ij}^{(0)} = 1$ when $i = j$ or $(i,j) \in E$. CLRS presents this in Section 25.2. For the four-vertex example below every vertex reaches every other, so the closure is all ones. Delete the edge $2\to 1$, the only edge into vertex 1, and column 1 of the closure becomes $1, 0, 0, 0$: only vertex 1 itself reaches 1.

Pseudocode uses 1-based matrices and <- for assignment.

In-place variant. Drop the superscripts and update D[i,j] in the triple loop; the algorithm remains correct (CLRS Exercise 25.2-4).

The loop over $k$ must be outermost. The recurrence needs every entry of level $k-1$ before level $k$ starts. Writing the loops as for i, for j, for k (with $k$ innermost) computes each $D[i,j]$ once, from entries that may not be final yet. Counterexample: the path $1\to 2\to 4\to 3$ with every weight 1. With $k$ innermost, $D[1,3]$ is computed while $D[1,4]$ is still $\infty$ (column 3 comes before column 4), and no later step revisits $D[1,3]$. It ends at $\infty$ instead of 3. With $k$ outermost the answer is 3.

Time / space. $\Theta(n^3)$ time, $\Theta(n^2)$ space. Independent of the number of edges, so dense graphs are the natural fit. For sparse nonnegative graphs, $n$ Dijkstra runs in $O(VE\lg V)$ can be faster.

Reconstruction. Keep a predecessor matrix $\pi_{ij}$: initially $\pi_{ij} = i$ if $(i,j) \in E$ and NIL otherwise; when the path through $k$ improves $i\to j$, set $\pi_{ij} \leftarrow \pi_{kj}$. Recursively print the path from $i$ to $\pi_{ij}$ then the edge to $j$. In the example below, $\pi_{1,3} = 4$ and $\pi_{1,4} = 1$, so the path is $1\to 4\to 3$ of weight $5 + 2 = 7$.

Edge cases. Missing edges start as $\infty$; $\infty + x = \infty$. Initialize off-diagonal $W[i,j]$ to the minimum weight among direct edges from $i$ to $j$, or $\infty$ if none exists. Initialize $W[i,i]=\min(0,\text{minimum self-loop weight at }i)$, interpreting a missing self-loop as $\infty$. A negative self-loop must be retained; it is already a negative cycle.

A shortest $i\to j$ path that uses intermediate vertices from $\{1,\ldots,k\}$ either avoids $k$ entirely (then it equals the $(k-1)$ answer) or splits as a shortest $i\to k$ path and a shortest $k\to j$ path, both using intermediates from $\{1,\ldots,k-1\}$. Those are the only two options, justifying the recurrence.

Johnson's algorithm reweights by a Bellman-Ford potential then runs Dijkstra from every vertex; it is the sparse-graph alternative when negatives appear but no negative cycle exists.

Weight matrix $W$ ($0$ on the diagonal, $\infty$ written as inf):

After $k=1$ (through vertex 1): $d_{2,4}$ stays 4; $d_{2,1}+d_{1,4}=2+5=7$ does not improve. After $k=2$: $d_{3,1}$ becomes $1+2=3$, $d_{3,4}$ becomes $1+4=5$. After $k=3$: $d_{4,1}$ becomes $2+3=5$, $d_{4,2}$ becomes $2+1=3$. After $k=4$: $d_{1,3}$ becomes $5+2=7$, $d_{2,3}$ becomes $4+2=6$. Final matrix:

All diagonal entries are 0, so no negative cycle.

Change $w_{4,1}$ from $\infty$ to $-10$. The cycle $1\to 4\to 1$ has weight $5 - 10 = -5$. After round $k = 4$, $d_{1,1}$, $d_{4,4}$ and $d_{2,2}$ are negative (vertex 2 lies on the cycle $2\to 4\to 1\to 2$ of weight $4 - 10 + 3 = -3$). $d_{3,3}$ stays 0: every cycle through vertex 3 has positive weight, even though 3 can reach a negative cycle. A zero diagonal entry does not rule out reaching a negative cycle; it does not rule out a negative closed walk through the vertex, obtained by repeating a reachable negative cycle sufficiently often and returning.

When the triple loop updates $D[i,j]$ in place, the right-hand side reads $D[i,k]$ and $D[k,j]$. These two entries do not change during round $k$: $d_{ik}^{(k)} = \min(d_{ik}^{(k-1)}, d_{ik}^{(k-1)} + d_{kk}^{(k-1)})$, and $d_{kk} = 0$ when there is no negative cycle, so row $k$ and column $k$ are the same at levels $k-1$ and $k$. Overwriting one matrix is therefore exactly as good as keeping two. The same in-place trick is not safe for every DP; matrix-chain multiplication, for example, needs the strict length order.

Floyd-Warshall offers no useful early termination: even if a round leaves the matrix unchanged, later $k$ values can still improve entries. Space is $\Theta(n^2)$ for distances plus $\Theta(n^2)$ if a full predecessor matrix is stored. For a single pair query on a sparse nonnegative graph, a bidirectional Dijkstra is preferable; Floyd-Warshall earns its keep when many pairs are needed or when negatives appear without a cycle.