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⇝k$ and $k⇝j$, each using only $\{1,\dots ,k-1\}$ as intermediates. That gives the two-case recurrence: $$d_{ij}^{(k)}=\min (d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}),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\times 5$ distance matrix shown in the exercise below. Notice the matrix is not symmetric — the graph is directed.