All-pairs shortest paths: Floyd-Warshall

All-pairs shortest paths

Sometimes you need $\delta(i,j)$ for every pair of vertices, not just from one source — an $n\times n$ distance matrix $D$. You *could* run a single-source algorithm $|V|$ times, but Floyd-Warshall solves it directly in $\Theta(V^3)$ for arbitrary (including negative) edge weights, with a clean DP.

The DP over intermediate vertices

The insight is to parameterize by *which vertices are allowed in the middle of a path*. Define $d_{ij}^{(k)}$ as the weight of a shortest path from $i$ to $j$ whose intermediate vertices all come from $\{1,\dots,k\}$. Now consider a shortest such path: either vertex $k$ is *not* an intermediate (so the path is already optimal using $\{1,\dots,k-1\}$), or it *is* — and then it splits into $i\rightsquigarrow k$ and $k\rightsquigarrow j$, each using only $\{1,\dots,k-1\}$ as intermediates. That gives the two-case recurrence: $$d_{ij}^{(k)}=\min\bigl(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\bigr),\qquad d_{ij}^{(0)}=w_{ij}.$$ The base $w_{ij}$ is the direct edge weight ($0$ on the diagonal, $\infty$ if no edge). The final matrix $D^{(n)}$ holds the true shortest distances $\delta(i,j)$.

Running time, space, and negative cycles

Three nested loops — $k$ outermost, then $i$, then $j$ — give $\Theta(V^3)$, with only $O(V^2)$ space if you overwrite the matrix in place. The algorithm handles negative edges, and a negative-weight cycle reveals itself as a negative diagonal entry $d_{ii}<0$ (a path from a vertex back to itself that costs less than $0$). For sparse graphs, Johnson's algorithm reweights via Bellman-Ford and runs $V$ Dijkstras for $O(V^2\lg V + VE)$ — faster than $\Theta(V^3)$ when $E$ is small.

Worked example

On the CLRS Fig 23.1 graph (5 vertices, several negative edges, no negative cycle) Floyd-Warshall produces the full $5\times5$ distance matrix shown in the exercise below. Notice the matrix is *not* symmetric — the graph is directed.