Floyd-Warshall Algorithm

Overview

Floyd-Warshall solves the all-pairs shortest paths (APSP) problem using dynamic programming. It is particularly suited to dense graphs, running in $\Theta(|V|^3)$ time and $\Theta(|V|^2)$ space (in-place optimisation). It handles negative edge weights but, like all shortest-path algorithms, requires that no negative-weight cycles exist.

The DP Recurrence

Number the vertices $1, 2, \ldots, n$. Let $d_{ij}^{(k)}$ be the weight of a shortest path from $i$ to $j$ using only intermediate vertices from the set $\{1, 2, \ldots, k\}$. The base case $k=0$ uses no intermediate vertices:

$d_{ij}^{(0)} = \begin{cases} 0 & \text{if } i = j \\ w(i, j) & \text{if } (i, j) \in E \\ \infty & \text{otherwise} \end{cases}$

For $k \ge 1$, vertex $k$ is either used as an intermediate vertex or not:

$d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)},\; d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$

After $k = n$, we have the full all-pairs shortest distances.

Pseudocode

FLOYD-WARSHALL(W):
  n = number of vertices
  D^(0) = W            // W is the weight matrix (∞ for absent edges)
  for k = 1 to n:
    let D^(k) be a new n × n matrix
    for i = 1 to n:
      for j = 1 to n:
        D^(k)[i][j] = min(D^(k-1)[i][j],
                          D^(k-1)[i][k] + D^(k-1)[k][j])
  return D^(n)

Space optimisation: The $D^{(k-1)}$ matrix can be overwritten to produce $D^{(k)}$ in place because $d_{ik}^{(k-1)} = d_{ik}^{(k)}$ and $d_{kj}^{(k-1)} = d_{kj}^{(k)}$ (paths where $k$ is an intermediate vertex cannot have $k$ as an endpoint). So a single $n \times n$ matrix suffices.

Worked Example

Consider a graph with $V = \{1,2,3,4\}$, edges and weights:

$W = D^{(0)} = \begin{pmatrix} 0 & 3 & \infty & 7 \\ 8 & 0 & 2 & \infty \\ 5 & \infty & 0 & 1 \\ 2 & \infty & \infty & 0 \end{pmatrix}$

$k=1$ (intermediate vertex {1}):

• $d_{2,3}^{(1)} = \min(d_{2,3}^{(0)}, d_{2,1}^{(0)} + d_{1,3}^{(0)}) = \min(2, 8+\infty) = 2$
• $d_{2,4}^{(1)} = \min(\infty, 8+7) = 15$
• $d_{3,2}^{(1)} = \min(\infty, 5+3) = 8$
• $d_{4,2}^{(1)} = \min(\infty, 2+3) = 5$

$D^{(1)} = \begin{pmatrix} 0 & 3 & \infty & 7 \\ 8 & 0 & 2 & 15 \\ 5 & 8 & 0 & 1 \\ 2 & 5 & \infty & 0 \end{pmatrix}$

$k=2$ (intermediate vertices {1,2}):

• $d_{1,3}^{(2)} = \min(\infty, 3+2) = 5$
• $d_{3,4}^{(2)} = \min(1, 8+15) = 1$
• $d_{4,3}^{(2)} = \min(\infty, 5+2) = 7$

$D^{(2)} = \begin{pmatrix} 0 & 3 & 5 & 7 \\ 8 & 0 & 2 & 15 \\ 5 & 8 & 0 & 1 \\ 2 & 5 & 7 & 0 \end{pmatrix}$

$k=3$ (intermediate vertices {1,2,3}):

• $d_{4,4}^{(3)} = \min(0, 7+1) = \min(0,8) = 0$ (no change).

$D^{(3)} = \text{(same as $D^{(2)}$, no new paths)}$

$k=4$:

• $d_{1,4}^{(4)} = \min(7, 7+0) = 7$ (unchanged)
• All others checked; no improvements.

$D^{(4)} = D^{(2)}$

The final matrix gives all-pairs distances. For example, $\delta(4,3) = 7$ via path $4 \to 1 \to 2 \to 3$ (cost $2+3+2=7$).

Predecessor Matrix

To reconstruct paths, maintain a predecessor matrix $\Pi^{(k)}$ in parallel. Initialise $\pi_{ij}^{(0)} = i$ if $(i,j) \in E$ or $i = j$, else NIL. Update alongside the distance matrix: if the $d_{ik} + d_{kj}$ path is chosen, set $\pi_{ij}^{(k)} = \pi_{kj}^{(k-1)}$.

Transitive Closure

Floyd-Warshall can compute the transitive closure $G^*$ of a graph: an edge $(i,j)$ exists in $G^*$ iff there is a path from $i$ to $j$ in $G$. Replace MIN with logical OR and $+$ with logical AND. Initialise $d_{ij}^{(0)} = 1$ if $i = j$ or $(i,j) \in E$, 0 otherwise. Running the same triple loop yields the reachability matrix in $\Theta(|V|^3)$.

For DAGs, the transitive closure can be computed more efficiently by processing vertices in topological order.

Comparison with Johnson

Algorithm	Time	Space	Best for
Floyd-Warshall	$\Theta(V^3)$	$\Theta(V^2)$	Dense graphs
Johnson	$O(V^2 \log V + VE)$	$\Theta(V^2)$	Sparse graphs

When $|E| = \Theta(|V|^2)$, both are $\Theta(|V|^3)$, but Floyd-Warshall has lower constant factors and is simpler to implement.

Summary

Property	Detail
Type	Dynamic programming
Recurrence	$d_{ij}^{(k)} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)})$
Base case	$d_{ij}^{(0)} = w(i,j)$ or 0 for $i=j$
Time	$\Theta(V^3)$
Space	$\Theta(V^2)$ (in-place)
Negative weights	Handled (no negative cycles)
Transitive closure	Replace min/+ with OR/AND

Past paper questions: y2026p1q10(c,d) (DAG transitive closure optimisation).