Floyd-Warshall Algorithm

Let $G = (V, E)$ be a directed graph with $n = |V|$ vertices, labeled $1$ through $n$, and a weight function $w$ on edges that may include negative weights but no negative-weight cycle overall (the algorithm can detect cycles that violate this). The goal is the all-pairs shortest path problem: compute, for every ordered pair $(i, j)$, the weight of a shortest path from $i$ to $j$, denoted $\delta(i, j)$. The key idea is to parametrize paths by which vertices they are permitted to pass through internally. Define $d_k(i, j)$ as the weight of a shortest path from $i$ to $j$ using only vertices from $\{1, 2, \dots, k\}$ as intermediate (interior) vertices — the endpoints $i$ and $j$ themselves are always allowed regardless of whether they lie in $\{1,\dots,k\}$. When $k = 0$, no intermediate vertices are allowed at all, so $d_0(i,j)$ is just the direct edge weight $w(i,j)$ if the edge exists, $0$ if $i = j$, and $\infty$ otherwise. When $k = n$, every vertex is an allowed intermediate, so $d_n(i,j) = \delta(i,j)$, the true shortest-path distance. The recurrence connecting consecutive stages is the heart of the method. A shortest path from $i$ to $j$ restricted to intermediates in $\{1,\dots,k\}$ either avoids vertex $k$ entirely — in which case it is already optimal using only $\{1,\dots,k-1\}$ — or it passes through $k$ exactly once (a shortest path never visits the same vertex twice, assuming no negative cycles), splitting into a sub-path from $i$ to $k$ and a sub-path from $k$ to $j$, both restricted to intermediates in $\{1,\dots,k-1\}$:

This is a textbook dynamic-programming recurrence: overlapping subproblems (many pairs share the same $d_{k-1}$ values) and optimal substructure (a shortest path's sub-paths are themselves shortest). Because $d_k$ depends only on $d_{k-1}$, the algorithm can reuse a single $n \times n$ matrix in place, updating it k by k, which is what gives the method its compact, loop-based implementation.

The algorithm maintains an $n \times n$ distance matrix $D$, initialized from the direct edge weights, and optionally a predecessor matrix $\Pi$ for path reconstruction. It then performs $n$ rounds, one per candidate intermediate vertex $k$, and in each round relaxes every pair $(i, j)$ using $k$ as a potential waypoint. Because $D$ is updated in place, the pseudocode never needs to keep the old and new matrices separate — this is legal precisely because $d_k(i, k)$ and $d_k(k, j)$ are provably equal to $d_{k-1}(i,k)$ and $d_{k-1}(k,j)$ respectively (routing through $k$ itself as an intermediate to reach $k$ cannot help, since that would require a negative-weight cycle through $k$), so overwriting row $k$ and column $k$ during round $k$ does not corrupt the values the recurrence needs. ``` FLOYD-WARSHALL(W, n): // W is an n x n matrix: W[i][j] = weight of edge i->j, // 0 if i = j, and +infinity if no edge exists. D = copy of W Pi = n x n matrix, Pi[i][j] = i if W[i][j] < infinity and i != j, else NIL for k = 1 to n: for i = 1 to n: for j = 1 to n: if D[i][k] + D[k][j] < D[i][j]: D[i][j] = D[i][k] + D[k][j] Pi[i][j] = Pi[k][j] // Negative-cycle check for i = 1 to n: if D[i][i] < 0: report "negative-weight cycle reachable from and to vertex i" return D, Pi ``` ``` RECONSTRUCT-PATH(Pi, i, j): if i == j: return [i] if Pi[i][j] == NIL: return "no path" path = RECONSTRUCT-PATH(Pi, i, Pi[i][j]) append j to path return path ``` A few implementation notes worth internalizing:

• The loop order must be $k$ outermost, then $i$, then $j$ (or $i$, $j$ swapped — order between them doesn't matter, but $k$ must be outermost). This is what guarantees that when computing $d_k(i,j)$, the matrix already holds $d_{k-1}$ values for all the entries the recurrence reads.
• The predecessor update `Pi[i][j] = Pi[k][j]` records that the shortest known $i \to j$ path now arrives at $j$ the same way the shortest $k \to j$ path does — because the new path is "old $i \to k$ path" followed by "old $k \to j$ path," and the predecessor of $j$ on that concatenation is whatever preceded $j$ on the $k \to j$ leg.
• Detecting negative cycles by scanning the diagonal works because $D[i][i]$ starts at $0$ and can only become negative if some cycle through $i$ (via allowed intermediates) has negative total weight.

Time complexity. The algorithm executes three nested loops, each running exactly $n$ times, and the body of the innermost loop does $O(1)$ work (one comparison, possibly one assignment). This gives

with no dependence on the number of edges $E$. This is a deliberate and important design point: for dense graphs, where $E = \Theta(V^2)$, running Dijkstra's algorithm from every vertex costs $O(V \cdot (E + V\log V)) = O(V^3)$ with a Fibonacci heap — asymptotically comparable — but Floyd-Warshall achieves this with far smaller constants and no data structure overhead (no heaps, no priority queue bookkeeping), and it works unmodified with negative edge weights, which Dijkstra's algorithm cannot handle directly. Running the Bellman-Ford algorithm from every source costs $O(V^2 E)$, which is asymptotically worse than $\Theta(V^3)$ whenever $E = \omega(V)$, making Floyd-Warshall preferable on dense graphs even though both handle negative weights.

Space complexity. The algorithm needs $\Theta(V^2)$ space for the distance matrix and, if paths must be reconstructed, another $\Theta(V^2)$ for the predecessor matrix. This is optimal in the sense that the output itself — the full pairwise distance matrix — already requires $\Theta(V^2)$ space to store.

Correctness proof sketch. The proof is by induction on $k$, formalizing the recurrence from the idea section. Claim: after the round for a given $k$ completes, $D[i][j] = d_k(i,j)$ for all pairs $(i,j)$, where $d_k(i,j)$ is the true shortest-path distance using only intermediates from $\{1,\dots,k\}$. Base case ($k=0$): before any round runs, $D$ holds the initial matrix $W$, which is exactly $d_0(i,j)$: the direct edge weight or $0$ or $\infty$, since no intermediate vertices are allowed. Inductive step: assume $D$ holds $d_{k-1}$ values entering round $k$. Consider any pair $(i,j)$ and let $P$ be a shortest path from $i$ to $j$ restricted to intermediates in $\{1,\dots,k\}$. Two cases: 1. $P$ does not use vertex $k$ as an interior vertex. Then $P$ is a path with intermediates only in $\{1,\dots,k-1\}$, so its weight is at least $d_{k-1}(i,j)$, and since $d_{k-1}(i,j)$ is itself achievable with intermediates in $\{1,\dots,k-1\} \subset \{1,\dots,k\}$, we get $d_k(i,j) = d_{k-1}(i,j)$ in this case. 2. $P$ does use vertex $k$ as an interior vertex. Because shortest paths (under the no-reachable-negative-cycle assumption) never repeat a vertex, $k$ appears exactly once, splitting $P$ into $P_1: i \to k$ and $P_2: k \to j$, each using only intermediates from $\{1,\dots,k-1\}$ (they cannot reuse $k$). By optimal substructure, $P_1$ and $P_2$ must themselves be shortest paths for their respective restricted problems — otherwise $P$ could be shortened — so weight$(P) = d_{k-1}(i,k) + d_{k-1}(k,j)$. Taking the minimum over both cases gives exactly the recurrence $d_k(i,j) = \min(d_{k-1}(i,j),\, d_{k-1}(i,k)+d_{k-1}(k,j))$, which is precisely the update the pseudocode performs, reading old ($k-1$-stage) values because rows/columns $k$ have not yet been altered by this round in a way that invalidates them (row $k$ and column $k$ are unchanged during round $k$, since $D[k][k]$ can't improve via itself without a negative cycle, and any update to $D[k][j]$ via $D[k][k]+D[k][j]$ is a no-op unless $D[k][k]<0$). This closes the induction, so after round $n$, $D[i][j] = d_n(i,j) = \delta(i,j)$ for all pairs.

Negative cycles. If a negative-weight cycle is reachable from $i$ and reaches back to $i$, then $\delta(i,i)$ is not well-defined (a walk around the cycle repeatedly decreases cost without bound), and the algorithm will compute $D[i][i] < 0$ for some $i$ once $k$ reaches a vertex on that cycle — this is exactly why the diagonal check at the end is a valid and complete negative-cycle detector. If no negative cycle exists anywhere in the graph, all shortest paths are simple (no repeated vertices), which is precisely the assumption the case-2 argument above relies on.

Tradeoffs. The $\Theta(V^3)$ time is a hard floor for this method regardless of how sparse the graph is — Floyd-Warshall does not exploit sparsity at all, unlike Johnson's algorithm, which reweights edges and runs Dijkstra from each vertex in $O(V^2 \log V + VE)$, a better bound when $E \ll V^2$. Floyd-Warshall's advantages are its extreme simplicity, small constant factors, in-place matrix updates, and uniform handling of negative edges without needing a separate reweighting step.

Consider a small directed graph with vertices $\{1,2,3,4\}$ and edges (with weights, some negative):

The initial distance matrix $D^{(0)}$ (rows = from, columns = to, $\infty$ shown as `∞`):

Round $k=1$ (allow routing through vertex 1). Check every $(i,j)$ for improvement via $D[i][1]+D[1][j]$. Only row 2 has a finite entry to column 1 ($D[2][1]=4$), so candidates are $D[2][j]$ via $4 + D[1][j]$: $j=3$ gives $4+(-2)=2 <$ current $3$ — improves! Update $D[2][3]=2$. No other pair improves since only vertex 2 can reach vertex 1.

Round $k=2$ (allow routing through vertex 2). Rows with finite entry to column 2: row 4 ($D[4][2]=-1$). Candidates $D[4][j]$ via $-1 + D[2][j]$: $j=1$: $-1+4=3 < \infty$, improve $D[4][1]=3$. $j=3$: $-1+2=1 < \infty$, improve $D[4][3]=1$. ($j=2$ is self, skip.)

Round $k=3$ (allow routing through vertex 3). Rows with finite entry to column 3: row 1 ($-2$), row 2 ($2$), row 4 ($1$). For each, add $D[\cdot][3] + D[3][j]$ and compare to $D[\cdot][j]$; only $D[3][4]=2$ is finite for $j\ne3$.

• Row 1: $D[1][3]+D[3][4] = -2+2 = 0 < \infty$ → update $D[1][4]=0$.
• Row 2: $D[2][3]+D[3][4] = 2+2 = 4 < \infty$ → update $D[2][4]=4$.
• Row 4: $D[4][3]+D[3][4] = 1+2 = 3$, current $D[4][4]=0$, no improvement.

Round $k=4$ (allow routing through vertex 4). Column 4 finite entries: rows 1 ($0$), 2 ($4$), 3 ($2$). Row 4 itself gives $D[4][j]$.

• Row 1 via 4: $D[1][4]+D[4][j]$: $j=2$: $0+(-1)=-1 < \infty$ → update $D[1][2]=-1$. $j=1$: $0+3=3$, no change to diagonal needed (would be $D[1][1]$, stays 0, correctly no negative cycle). $j=3$: $0+1=1$, current $-2$, no improvement.
• Row 2 via 4: $4 + D[4][j]$: $j=1$: $4+3=7 > 4$, no. $j=2$: would be self, skip. $j=3$: $4+1=5>2$, no.
• Row 3 via 4: $2+D[4][j]$: $j=1$: $2+3=5<\infty$ → update $D[3][1]=5$. $j=2$: $2+(-1)=1<\infty$ → update $D[3][2]=1$.

Final matrix $D^{(4)} = \delta$:

All diagonal entries remain $0$, so there is no negative-weight cycle. Sanity-check one entry by hand: $\delta(1,2) = -1$ corresponds to the path $1 \to 3 \to 4 \to 2$ with weight $-2+2+(-1) = -1$, matching the direct-edge check ($1\to2$ has no direct edge) — confirming the dynamic program found a genuinely non-obvious multi-hop shortest path.

The algorithm's dynamic-programming core — reasoning about paths restricted to a growing set of allowed intermediate vertices — was published by Robert Floyd in 1962 as a concise procedure for shortest paths, building on a closely related transitive-closure algorithm published by Stephen Warshall in the same year. Bernard Roy had independently described an essentially equivalent algorithm in 1959 for the related problem of computing transitive closure and shortest paths, which is why some treatments call it the Roy-Floyd-Warshall or Roy-Warshall algorithm. The recurrence itself echoes ideas from dynamic programming as formalized by Richard Bellman in the 1950s, and the entire family of algorithms sits within the broader tradition of the Bellman Equation style of reasoning about optimal substructure.

Network routing and traffic engineering systems use all-pairs shortest-path precomputation to answer "what is the best path between any two routers" queries instantly without recomputation, especially in software-defined networking controllers managing moderately sized dense topologies. Compilers and static analyzers use Floyd-Warshall-style transitive-closure computations for reachability analysis, alias analysis, and certain forms of dataflow analysis, where the "graph" is a control-flow or points-to graph and the goal is Boolean or weighted reachability between all pairs of program points. Game AI and pathfinding systems on relatively small, dense maps (grid regions, building interiors) sometimes precompute all-pairs distances offline with Floyd-Warshall so that at runtime any two points can be connected with an O(1) table lookup rather than an online search — a classic space-for-time tradeoff. Database query optimizers use related matrix-closure computations to estimate cheapest join orderings across many tables. Computational biology tools apply the same recurrence to interaction networks and metabolic pathway graphs to compute pairwise "distances" (interaction costs) between all molecules or genes in a dense subnetwork. More broadly, the algorithm is a canonical teaching example for the Dynamic Programming paradigm and is frequently contrasted with single-source methods like Dijkstra's Algorithm and Bellman-Ford Algorithm to illustrate when a dense, uniform, matrix-based approach outperforms repeated single-source computations, and it serves as the conceptual ancestor of Kleene's algorithm for regular expressions from finite automata, which uses an isomorphic intermediate-state recurrence.

Ask the tutor: How would you modify Floyd-Warshall to count the number of distinct shortest paths between every pair, not just their lengths?