Floyd-Warshall Algorithm

Floyd-Warshall algorithm (also known as the Roy–Warshall–Floyd algorithm) is a classic dynamic programming method within computation and algorithms that solves the all-pairs shortest-path (APSP) problem on a weighted directed graph G = (V, E, w) in Θ(|V|³) time and Θ(|V|²) space. In a single execution of three nested loops over the vertex indices {1, 2, ..., |V|}, the algorithm computes the minimum-weight directed path distance δ(i, j) between every ordered pair of vertices (i, j) ∈ V × V, accommodating positive and negative edge weights provided the graph contains no negative-weight cycles.

Discovered independently across three mathematical domains—by Bernard Roy in 1959 for graph path connectivity, by Stephen Warshall in January 1962 for the Boolean transitive closure of binary relations, and by Robert W. Floyd in June 1962 as Algorithm 97 in Communications of the ACM—the algorithm executes branch-free, stride-1 matrix operations without priority-queue pointer overhead. Consequently, the Floyd-Warshall algorithm remains a standard tool for dense graphs (where |E| = Θ(|V|²)), all-pairs patristic distance matrices in bioinformatics, and Kleene closure computations over closed semirings.

Subproblem Parameterization by Intermediate Vertex Set

Let the vertices of G = (V, E, w) be numbered V = {1, 2, ..., n}. Rather than inducting on edge count as the Bellman-Ford algorithm does, Floyd's recurrence restricts the intermediate vertices permitted along a path. An intermediate vertex of a simple path p = ⟨v₀, v₁, ..., v_r⟩ is any interior vertex v_m ∈ {v₁, ..., v_r−1} excluding the endpoints v₀ and v_r.

For any subset prefix V_k = {1, 2, ..., k} with 0 ≤ k ≤ n, define d^(k)(i, j) as the minimum weight of any directed path from vertex i to vertex j whose intermediate vertices belong to {1, 2, ..., k}. At base case k = 0 (V₀ = ∅, no intermediate vertices allowed), a path from i to j uses at most a single direct edge (i, j) ∈ E:

Optimal Substructure and the Cubic Recurrence

Assuming G contains no negative-weight cycles, every shortest path is simple and visits any intermediate vertex k at most once. When advancing from stage k − 1 to stage k (for k = 1, 2, ..., n), any shortest path p from i to j using intermediate vertices in {1, ..., k} falls into one of two cases:

1. Vertex k is not an intermediate vertex of p: All intermediate vertices of p belong to {1, ..., k − 1}, so the path weight is d^(k−1)(i, j).
2. Vertex k is an intermediate vertex of p: Because p is simple, p visits k once and splits into a subpath p₁ from i to k followed by a subpath p₂ from k to j, where both subpaths use intermediate vertices only from {1, ..., k − 1}.

Taking the minimum of these two cases yields the Floyd-Warshall recurrence equation:

At k = n, the permitted intermediate set {1, ..., n} equals V, giving d⁽ⁿ⁾(i, j) = δ(i, j) for all (i, j) ∈ V × V.

Space Compression to Θ(|V|²) and Negative-Cycle Diagnostics

During stage k, pivot row k and pivot column k remain invariant because d^(k)(i, k) = min{d^(k−1)(i, k), d^(k−1)(i, k) + d^(k−1)(k, k)} = d^(k−1)(i, k) whenever d^(k−1)(k, k) ≥ 0. Consequently, all updates execute in-place within a single n × n matrix D[i, j]:

Placing the intermediate pivot k as the outermost loop is mandatory; nesting k innermost only inspects two-hop paths. A companion n × n successor table *Next*[i, j] (updated via *Next*[i, j] ← *Next*[i, k] whenever D[i, k] + D[k, j] < D[i, j]) reconstructs the shortest path in O(length) hops, while negative diagonal entries (D[i, i] < 0) detect negative-weight cycles passing through vertex i.

Warshall's Transitive Closure and Closed Semirings

Peter Ingerman (1962) and Alfred Aho, John Hopcroft, and Jeffrey Ullman (1974) showed that Warshall's transitive closure, Floyd's shortest paths, and Kleene's finite-automaton-to-regular-expression conversion are instances of Gauss–Jordan elimination over a closed semiring (or Kleene algebra) (S, ⊕, ⊗, 0̄, 1̄):

Substituting different algebraic semirings into the identical triple-loop template solves distinct problems across computational complexity theory:

The APSP Conjecture, Tropical Semiring, and Scientific Applications

In the min-plus (tropical) semiring (ℝ ∪ {+∞}, min, +), the min operator lacks an additive inverse (subtraction), preventing direct application of Strassen-style fast divide-and-conquer algorithm matrix multiplication. Within fine-grained complexity theory, the All-Pairs Shortest Paths (APSP) Hypothesis conjectures that no algorithm solves general weighted APSP in truly subcubic O(n^3−ε) time for any ε > 0; the fastest known upper bound is Ryan Williams's 2014 circuit-polynomial algorithm running in O(n³ / exp(Ω((log n)^1/2))) time.

In molecular phylogenetics and neighbor-joining, the Floyd-Warshall algorithm enforces metric triangle-inequality closure on incomplete evolutionary distance matrices derived from sequence alignment. In structural biology, it performs NMR nuclear Overhauser effect (NOE) distance-restraint bound smoothing prior to 3D coordinate embedding, and in network science it computes graph diameter, Wiener indices, and closeness centrality across protein–protein interaction networks.

When is the Floyd-Warshall algorithm faster than running Dijkstra's algorithm from every vertex?

On a sparse graph (|E| = O(|V|)), running Dijkstra's algorithm |V| times takes O(|V|² log |V| + |V|·|E|) = O(|V|² log |V|) time, beating Θ(|V|³). On a dense graph (|E| = Θ(|V|²)), however, repeated Dijkstra performs O(|V|³) work with heavy heap-pointer overhead, whereas Floyd-Warshall's branchless inner loop vectorizes across SIMD lanes and GPUs, outperforming repeated Dijkstra on dense matrices.

How does the Floyd-Warshall algorithm detect negative-weight cycles?

Diagonal entries start at D[i, i] = 0. During execution, D[i, i] is updated to D[i, k] + D[k, i] whenever a closed walk from i through k and back to i has negative total weight. Thus, G has a negative-weight cycle if and only if D[i, i] < 0 for some vertex i upon termination.

1. Roy, B. (1959). "Transitivité et connexité." Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 249, 216–218. https://doi.org/10.1016/S0019-9958(59)90362-690362-6)
2. Warshall, S. (1962). "A theorem on Boolean matrices." Journal of the ACM, 9(1), 11–12. https://doi.org/10.1145/321105.321107
3. Floyd, R. W. (1962). "Algorithm 97: Shortest path." Communications of the ACM, 5(6), 345. https://doi.org/10.1145/367766.368168
4. Williams, R. (2018). "Faster all-pairs shortest paths via circuit complexity." SIAM Journal on Computing, 47(5), 1965–1985. https://doi.org/10.1137/15M1024524