47.04.05 · theoretical-cs / algorithms-analysis

All-Pairs Shortest Paths: Floyd-Warshall and Johnson's Algorithm

shipped3 tiersLean: none

Anchor (Master): Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §25.1-25.3; Tarjan 1983 Data Structures and Network Algorithms (SIAM) Ch. 7 (all-pairs shortest paths, relationship to matrix multiplication over semirings, Floyd-Warshall as min-plus matrix multiplication)

Intuition Beginner

You have a road map with cities as vertices and roads as edges, each with a travel time. You want to know the fastest route between every pair of cities, not just two specific ones. This is the all-pairs shortest-paths problem.

One approach: run Dijkstra's algorithm from every city. This works but can be slow if the map is dense. A different approach, Floyd-Warshall, asks a clever question: what is the shortest path from city A to city B if you are only allowed to pass through the first $k$ cities as intermediate stops?

As $k$ grows from 0 to $n$ , the answer gets better and better. When $k = 0$ , you can only use direct roads. When $k = 1$ , you can also stop at city 1. When $k = n$ , you can stop anywhere, and you have the true shortest paths.

Each step is simple: the shortest path from A to B using cities ${1, \dots, k}$ either does not use city $k$ (so it equals the previous answer) or does use city $k$ (so it is the shortest A-to- $k$ plus shortest $k$ -to-B). Take the minimum of these two options.

Johnson's algorithm takes a different approach. It handles negative edge weights by "reweighting" the graph so that all weights become non-negative, then runs Dijkstra from every vertex. The reweighting preserves shortest paths, so the answers are correct.

Visual Beginner

A weighted graph with 4 vertices:

    2         5
 (0)───→(1)───→(2)
  │      ↑      │
  │  -1  │  1   │
  ↓      │      ↓
 (3)─────┘     (4)
       3

Wait, let me simplify. A 4-vertex graph:

     3        1
 0 ──→ 1 ──→ 2
 │            ↑
 │ 8          │ 2
 ↓            │
 3 ──────────┘
       5

Floyd-Warshall fills in a distance matrix step by step.

Step	0→1	0→2	0→3	1→2
k=0	3	inf	8	1
k=1	3	4	8	1
k=2	3	4	8	1
k=3	3	4	8	1

At $k = 1$ : shortest 0→2 using intermediate {1} = min(4, 3+1) = 4. At $k = 3$ : shortest 0→3 using {0,1,2,3} = min(8, 4+5+2...) already 8.

Worked example Beginner

We run Floyd-Warshall on a 4-vertex graph with edge weights:

0→1: 3, 0→3: 8, 1→2: 1, 2→3: 2, 3→1: -4.

Initial distance matrix ( $k = 0$ , only direct edges):

     0    1    2    3
0 [  0    3   ∞    8  ]
1 [  ∞    0    1   ∞  ]
2 [  ∞   ∞    0    2  ]
3 [  ∞   -4   ∞    0  ]

Step $k = 1$ (can use vertex 1 as intermediate):

0→2: min(∞, 3+1) = 4. 0→3: min(8, 3+∞) = 8. 3→2: min(∞, -4+1) = -3.

     0    1    2    3
0 [  0    3    4    8  ]
1 [  ∞    0    1   ∞  ]
2 [  ∞   ∞    0    2  ]
3 [  ∞   -4   -3    0  ]

Step $k = 2$ (can use vertices 1, 2):

0→3: min(8, 4+2) = 6. 1→3: min(∞, 1+2) = 3. 3→3: min(0, -3+2) = -1.

Wait — a negative diagonal entry means a negative cycle. Let me recalculate. 3→2→3 = -3+2 = -1. And 3→3 = 0. So min(0, -1) = -1. This indicates a negative-weight cycle through vertex 3.

Actually, let me redo with a graph that has no negative cycles. Remove the edge 3→1. Then:

Initial ( $k = 0$ ):

     0    1    2    3
0 [  0    3   ∞    8  ]
1 [  ∞    0    1   ∞  ]
2 [  ∞   ∞    0    2  ]
3 [  ∞   ∞    ∞    0  ]

$k = 1$ : 0→2: min(∞, 3+1) = 4. $k = 2$ : 0→3: min(8, 4+2) = 6. 1→3: min(∞, 1+2) = 3. $k = 3$ : no improvements (3 has no outgoing edges except to itself).

Final matrix:

     0    1    2    3
0 [  0    3    4    6  ]
1 [  ∞    0    1    3  ]
2 [  ∞   ∞    0    2  ]
3 [  ∞   ∞    ∞    0  ]

Shortest path 0→3: 0→1→2→3 with weight 3+1+2 = 6.

Check your understanding Beginner

Formal definition Intermediate+

Definition (all-pairs shortest-paths). Given a weighted directed graph $G = (V, E, w)$ with $w : E \to R$ and $∣ V ∣ = n$ , the all-pairs shortest-paths problem is to compute an $n \times n$ matrix $D$ where $D_{ij} = δ (i, j)$ , the weight of a shortest path from $i$ to $j$ , and a predecessor matrix $Π$ for path reconstruction.

Definition (Floyd-Warshall recurrence). Define $d_{ij}^{(k)}$ as the weight of a shortest path from $i$ to $j$ using only intermediate vertices from ${1, 2, \dots, k}$ . The recurrence is:

d_{ij}^{(0)} = ⎩ ⎨ ⎧ 0 w (i, j) \infty if i = j if (i, j) \in E otherwise

d_{ij}^{(k)} = min (d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)})

The final answer is $D_{ij} = d_{ij}^{(n)}$ .

Theorem (Floyd-Warshall correctness). If $G$ has no negative-weight cycles, then $d_{ij}^{(n)} = δ (i, j)$ for all $i, j$ .

Definition (Johnson's reweighting). Given $G = (V, E, w)$ , add a new vertex $s$ with zero-weight edges to all vertices. Run Bellman-Ford from $s$ to compute shortest-path distances $h (v) = δ (s, v)$ . Define the reweighted graph $\overset{w}{^} (u, v) = w (u, v) + h (u) - h (v)$ .

Lemma (reweighting preserves shortest paths). If $p = ⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$ is any path from $v_{0}$ to $v_{k}$ , then $\overset{w}{^} (p) = w (p) + h (v_{0}) - h (v_{k})$ . Therefore, $p$ is a shortest path under $w$ if and only if $p$ is a shortest path under $\overset{w}{^}$ .

Furthermore, if $G$ has no negative-weight cycles, then $\overset{w}{^} (u, v) \geq 0$ for all edges, enabling the use of Dijkstra's algorithm.

Counterexamples to common slips

"Running Dijkstra from every vertex solves APSP in $O (V E + V^{2} lo g V)$ ." This is correct only for non-negative edge weights. If the graph has negative edges (but no negative cycles), Dijkstra is incorrect and Johnson's reweighting is needed first.
"Floyd-Warshall is always slower than running Dijkstra $n$ times." For dense graphs ( $E = Θ (V^{2})$ ), Floyd-Warshall's $O (V^{3})$ matches $n$ runs of Dijkstra at $O (V^{2})$ each. For sparse graphs, $n$ Dijkstra runs take $O (V (V lo g V + E))$ which is faster.
"Johnson's algorithm requires no negative edges." Johnson's handles negative edges by reweighting them away. It requires no negative cycles, not no negative edges.

Key theorem with proof Intermediate+

Theorem (Floyd-Warshall correctness). For all $i, j$ and $k \in {0, \dots, n}$ , $d_{ij}^{(k)}$ equals the weight of a shortest path from $i$ to $j$ with all intermediate vertices in ${1, \dots, k}$ .

Proof. By induction on $k$ .

Base: $k = 0$ . No intermediate vertices are allowed, so the only paths are direct edges or the empty path (when $i = j$ ). $d_{ij}^{(0)}$ is set to exactly these values.

Inductive step: assume $d_{ij}^{(k - 1)}$ is correct. Consider a shortest path $p$ from $i$ to $j$ using intermediates in ${1, \dots, k}$ . Either $p$ does not use vertex $k$ as an intermediate, in which case $w (p) = d_{ij}^{(k - 1)}$ , or $p$ uses $k$ . In the latter case, $p$ decomposes as $i ⇝ k ⇝ j$ where the $i ⇝ k$ subpath uses intermediates in ${1, \dots, k - 1}$ (it cannot pass through $k$ before reaching $k$ ) and similarly for $k ⇝ j$ . So $w (p) = d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)}$ . Taking the minimum of these two options gives $d_{ij}^{(k)}$ . $□$

Bridge. The Floyd-Warshall recurrence is the foundational reason all-pairs shortest paths can be computed in $O (V^{3})$ time: it builds up the solution by progressively allowing more intermediate vertices, and each step is a simple minimisation. This builds toward the transitive closure computation, where the same structure appears with OR replacing MIN and AND replacing PLUS, and it appears again in min-plus matrix multiplication, where the Floyd-Warshall algorithm is exactly the computation of the closure of the weight matrix over the min-plus semiring. The central insight is that shortest paths compose: the shortest $i$ -to- $j$ path through $k$ is the concatenation of the shortest $i$ -to- $k$ and $k$ -to- $j$ paths. Putting these together with Johnson's reweighting yields a complete toolkit for APSP: Floyd-Warshall for dense or small graphs, Johnson for sparse graphs with negative edges.

Exercises Intermediate+

Exercise 1 (easy, symbolic).

Run one step of Floyd-Warshall ( $k = 1$ ) on the following initial distance matrix. Show the updated entries.

     1    2    3
1 [  0    4   ∞  ]
2 [  ∞    0    3  ]
3 [  2   ∞    0  ]

Answer

Allowing vertex 1 as intermediate:

3→2: min(∞, 2+4) = 6. 2→1: still ∞ (no 2→1 path through 1). 3→3: min(0, 2+∞) = 0.

Updated matrix:

     1    2    3
1 [  0    4   ∞  ]
2 [  ∞    0    3  ]
3 [  2    6    0  ]

Exercise 8 (hard, symbolic).

The min-plus product of two $n \times n$ matrices $A$ and $B$ is defined as $(A \otimes B)_{ij} = min_{k} (A_{ik} + B_{k j})$ . Show that Floyd-Warshall computes the min-plus closure of the weight matrix $W$ : the matrix $D = W \oplus W^{2} \oplus \dots \oplus W^{n}$ where $W^{k}$ is the $k$ -fold min-plus product.

Answer

$W^{k}$ (min-plus power) represents the shortest paths using exactly $k$ edges. $W^{1} = W$ (direct edges). $W^{2} = W \otimes W$ gives shortest 2-edge paths. The min-plus closure $D = W \oplus W^{2} \oplus \dots \oplus W^{n}$ takes the minimum over all path lengths from 1 to $n$ edges. Since a shortest path in an $n$ -vertex graph uses at most $n - 1$ edges (no negative cycles), this captures all shortest paths.

The Floyd-Warshall recurrence $d_{ij}^{(k)} = min (d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)})$ can be viewed as one step of min-plus matrix multiplication: $D^{(k)} = D^{(k - 1)} \oplus (D^{(k - 1)} \otimes D^{(k - 1)})$ restricted to paths through vertex $k$ . This is a structured version of computing the min-plus closure. Rubric: full credit for connecting the recurrence to the semiring framework.

Lean formalization Intermediate+

Mathlib has Graph.Weighted and basic graph definitions but no formalisation of Floyd-Warshall or Johnson's algorithm. The foundational gap is the absence of an APSP matrix computation with correctness proofs. The Floyd-Warshall recurrence and its inductive proof require a formalisation of "paths using intermediates in ${1, \dots, k}$ ." Johnson's reweighting requires the shortest-path potential $h (v)$ and the proof that $\overset{w}{^} (u, v) \geq 0$ . This unit ships without a lean_module.

Advanced results Master

Three results extend the basic APSP theory.

Theorem 1 (min-plus semiring). The Floyd-Warshall algorithm is a computation in the min-plus semiring $(R \cup {\infty}, min, +)$ . The distance matrix $D$ is the closure of the weight matrix $W$ in this semiring: $D = W^{*}$ where $W^{*} = I \oplus W \oplus W^{2} \oplus \dots$ .

This algebraic perspective unifies shortest paths with other semiring computations. Replacing $(min, +)$ with $(\lor, \land)$ gives transitive closure. Replacing with $(+, \times)$ gives matrix powers. The Floyd-Warshall algorithm is a specialisation of Kleene's algorithm for computing semiring closures ^{[Tarjan Ch. 7]}.

Theorem 2 (APSP via matrix multiplication). If $n \times n$ matrix multiplication over a ring can be done in time $O (n^{ω})$ , then APSP can be solved in $\tilde{O} (n^{2 + μ})$ time where $μ$ satisfies $ω (1, μ, 1) = 1 + 2 μ$ , using the relationship between min-plus products and standard matrix multiplication over appropriate rings.

The current best APSP algorithm for dense graphs is by Williams (2018), running in $n^{3} / 2^{Θ (l o g n)}$ time, using fast matrix multiplication techniques applied to the min-plus product.

Theorem 3 (negative cycle detection). Floyd-Warshall detects a negative-weight cycle if and only if some diagonal entry $d_{ii}^{(n)} < 0$ . The detection takes no additional time beyond the main algorithm.

Synthesis. The Floyd-Warshall and Johnson algorithms are the foundational reason APSP can be solved efficiently: Floyd-Warshall provides a simple $O (V^{3})$ solution for all graphs, while Johnson adapts Dijkstra to handle negative weights via reweighting. The central insight is that shortest paths compose — the path $i ⇝ k ⇝ j$ has weight equal to the sum of its parts — and this is exactly the property exploited by both algorithms. This builds toward the semiring generalisation, where the same algorithmic structure computes transitive closure, matrix powers, and other algebraic closures. Putting these together with the single-source shortest-path algorithms (Bellman-Ford, Dijkstra) yields a complete shortest-path toolkit: choose the algorithm based on graph density and edge weight properties.

Full proof set Master

Proposition 1 (Floyd-Warshall correctness). For all $k \in {0, \dots, n}$ and all $i, j$ , $d_{ij}^{(k)}$ equals the weight of a shortest path from $i$ to $j$ using only vertices in ${1, \dots, k}$ as intermediaries.

Proof. By strong induction on $k$ .

Base ( $k = 0$ ): No intermediate vertices. The only paths are direct edges (weight $w (i, j)$ ) or the identity path $i$ to $i$ (weight 0). $d_{ij}^{(0)}$ is defined to match these values exactly.

Inductive step: Assume the claim for $k - 1$ . Let $p$ be a shortest path from $i$ to $j$ using intermediates in ${1, \dots, k}$ .

Case 1: $p$ does not contain vertex $k$ . Then $p$ uses only intermediates in ${1, \dots, k - 1}$ , so $w (p) = d_{ij}^{(k - 1)}$ .

Case 2: $p$ contains vertex $k$ . Decompose $p$ as $i ⇝ k ⇝ j$ where both subpaths use only intermediates in ${1, \dots, k - 1}$ (if $k$ appeared in a subpath, it would create a cycle that could be removed without increasing weight, contradicting minimality). Then $w (p) = d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)}$ .

In either case, $w (p) \geq min (d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)}) = d_{ij}^{(k)}$ . And $d_{ij}^{(k)}$ is achievable by one of the two cases, so $w (p) = d_{ij}^{(k)}$ . $□$

Proposition 2 (Johnson's reweighting preserves shortest paths). Let $h : V \to R$ be any function satisfying $h (v) \leq h (u) + w (u, v)$ for all $(u, v) \in E$ . Define $\overset{w}{^} (u, v) = w (u, v) + h (u) - h (v)$ . Then $p$ is a shortest $s$ -to- $t$ path under $w$ iff $p$ is a shortest $s$ -to- $t$ path under $\overset{w}{^}$ .

Proof. For any path $p = ⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$ from $s = v_{0}$ to $t = v_{k}$ :

\overset{w}{^} (p) = i = 0 \sum k - 1 [w (v_{i}, v_{i + 1}) + h (v_{i}) - h (v_{i + 1})] = w (p) + h (s) - h (t) .

The offset $h (s) - h (t)$ depends only on the endpoints, not on the path. So if $p$ minimises $w (p)$ among all $s$ -to- $t$ paths, it also minimises $\overset{w}{^} (p) = w (p) + h (s) - h (t)$ , and vice versa. $□$

Proposition 3 (reweighting yields non-negative weights). If $G$ has no negative-weight cycles and $h (v) = δ (s, v)$ for an added source $s$ , then $\overset{w}{^} (u, v) \geq 0$ for all $(u, v) \in E$ .

Proof. By the triangle inequality for shortest paths, $h (v) \leq h (u) + w (u, v)$ for every edge $(u, v)$ . Rearranging: $w (u, v) + h (u) - h (v) \geq 0$ , i.e., $\overset{w}{^} (u, v) \geq 0$ . $□$

Connections Master

47.04.01 — Amortized analysis applies to sequences of shortest-path queries; the Floyd-Warshall algorithm precomputes all answers in one pass.
47.04.06 — MST algorithms find minimum-weight spanning subgraphs; APSP algorithms find minimum-weight paths. Both are fundamental graph optimisation primitives.
47.04.03 — Min-cost flow algorithms use shortest-path computations as a subroutine; Johnson's reweighting is used to handle negative reduced costs.
50.03.01 — Big-O analysis bounds the running times of both Floyd-Warshall ( $Θ (V^{3})$ ) and Johnson's ( $O (V E + V^{2} lo g V)$ ).

Historical & philosophical context Master

The Floyd-Warshall algorithm was published by Robert Floyd in 1962, though the same idea was discovered independently by Bernard Roy in 1959 and Stephen Warshall in 1962 (for transitive closure). The algorithm is an instance of a more general technique: computing the closure of a matrix over a closed semiring, as formalised by Lehmann (1977) and later by Tarjan ^{[CLRS §25.2 notes]}.

Johnson's algorithm was published by Donald Johnson in 1977. The key insight — that shortest-path potentials can be used to reweight edges non-negatively — is a discrete analogue of the concept of gauge transformations in physics, where a transformation preserves the physical content while simplifying the equations. The potential function $h (v)$ plays the role of a "gauge" that adjusts edge weights without changing shortest paths.

The APSP problem has deep connections to matrix multiplication. Subramanian (1991) and later Williams (2018) showed that APSP can be solved faster than $O (n^{3})$ using techniques from fast matrix multiplication, though the improvements are sub-polynomial. Whether APSP requires $Ω (n^{3})$ time in the worst case (without fast matrix multiplication) remains open and is one of the central questions in fine-grained complexity theory ^{[CLRS §25.2]}.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, Thomas H. and Leiserson, Ronald L. and Rivest, Clifford and Stein, Christopher},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@article{floyd1962algorithm,
  author  = {Floyd, Robert W.},
  title   = {Algorithm 97: Shortest Path},
  journal = {Communications of the ACM},
  volume  = {5},
  number  = {6},
  pages   = {345},
  year    = {1962},
}
@article{johnson1977efficient,
  author  = {Johnson, Donald B.},
  title   = {Efficient Algorithms for Shortest Paths in Sparse Networks},
  journal = {Journal of the ACM},
  volume  = {24},
  number  = {1},
  pages   = {1--13},
  year    = {1977},
}

Prerequisites

47.04.01

Tier anchors

beginner: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §25.1-25.2 (the all-pairs shortest-paths problem: finding the shortest distance between every pair of vertices, Floyd-Warshall's dynamic programming approach, Johnson's reweighting trick)
intermediate: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §25.1-25.3 (Floyd-Warshall recurrence and O(V^3) algorithm, Johnson's algorithm using Bellman-Ford reweighting plus Dijkstra for O(V^2 log V + VE) sparse graphs, transitive closure)
master: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §25.1-25.3; Tarjan 1983 Data Structures and Network Algorithms (SIAM) Ch. 7 (all-pairs shortest paths, relationship to matrix multiplication over semirings, Floyd-Warshall as min-plus matrix multiplication)

References

Cormen, T. H., Leiserson, R. L., Rivest, C. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 25.1 formulates the all-pairs shortest-paths (APSP) problem: given a weighted directed graph $G = (V, E, w)$ with $∣ V ∣ = n$ and weight function $w : E \to R$ , compute an $n \times n$ matrix $D$ where $D_{ij}$ is the weight of a shortest path from vertex $i$ to vertex $j$ ; Section 25.2 presents the Floyd-Warshall algorithm based on the recurrence $d_{ij}^{(k)} = min (d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)})$ where $d_{ij}^{(k)}$ is the shortest path from $i$ to $j$ using only vertices ${1, \dots, k}$ as intermediaries; the algorithm runs in $Θ (n^{3})$ time and $Θ (n^{2})$ space; Section 25.3 presents Johnson's algorithm which reweights edges using potentials from Bellman-Ford to eliminate negative weights, then runs Dijkstra from each vertex, achieving $O (n^{2} l g n + n E)$ time on sparse graphs.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m