Home › Computer Science › Algorithms › Floyd–Warshall Algorithm

Floyd–Warshall Algorithm

📊 Computer Science 🧮 Graph Theory ✓ AI-Verified 🕒 Last updated: Nov 14, 2025 👤 Dr. Elena Voss, Contributing Editor

The Floyd–Warshall algorithm is a dynamic programming algorithm used to compute the shortest paths between all pairs of vertices in a weighted graph[1]. Unlike single-source shortest path algorithms such as Dijkstra's or Bellman–Ford, Floyd–Warshall solves the all-pairs shortest path (APSP) problem in a single execution. It correctly handles graphs with negative edge weights, provided there are no negative cycles[2].

Developed independently by Robert W. Floyd, Stephen Warshall, and Peter Ingerman in the early 1960s, the algorithm remains a foundational concept in computer science, graph theory, and discrete mathematics due to its elegant recurrence relation and straightforward implementation[3].

History & Origins

The algorithm traces its origins to a 1962 paper by Peter Ingerman, who published it in the Communications of the ACM newsletter[4]. Stephen Warshall independently derived the transitive closure version in 1962, while Robert Floyd adapted it for weighted graphs and popularized it in a 1962 Communications of the ACM article. The name "Floyd–Warshall" was later formalized in academic literature to honor both primary contributors, though Ingerman's priority is now widely acknowledged in historical retrospectives[5].

Algorithm Description

The algorithm operates on an adjacency matrix dist of size V × V, where V is the number of vertices. Initially, dist[i][j] stores the weight of the direct edge from vertex i to j (or ∞ if no edge exists). The algorithm iteratively improves these estimates by considering each vertex k as a potential intermediate point on the shortest path between i and j.

The core recurrence relation is:

Mathematical Formulation
disti,j(k) = min(disti,j(k−1), disti,k(k−1) + distk,j(k−1))

After V iterations, dist[i][j] contains the shortest path distance between vertices i and j. If any diagonal entry dist[i][i] < 0, the graph contains a negative cycle reachable from vertex i[6].

Pseudocode

Language-agnostic Pseudocode
function FloydWarshall(graph): let dist be a |V| × |V| array initialized to ∞ for each vertex i: dist[i][i] = 0 for each edge (u, v) with weight w: dist[u][v] = w for k from 0 to |V| - 1: for i from 0 to |V| - 1: for j from 0 to |V| - 1: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist

Complexity Analysis

  • Time Complexity: O(|V|³) due to three nested loops iterating over all vertices. The constant factor is extremely small, making it competitive for dense graphs.
  • Space Complexity: O(|V|²) to store the distance matrix. Space can be reduced to O(1) auxiliary by updating in-place, though this prevents path reconstruction without additional storage.
  • Parallelization: The algorithm exhibits high parallel complexity but low work efficiency on PRAM models. GPU-accelerated implementations achieve near-linear speedups for large adjacency matrices[7].

💡 Practical Note: For sparse graphs, running Dijkstra's algorithm from each vertex (O(|V|·|E| log |V|)) or Johnson's algorithm (O(|V|² log |V| + |V||E|)) is typically more efficient.

Applications

Beyond basic shortest-path computation, the Floyd–Warshall algorithm enables several critical graph-theoretic operations:

  • Transitive Closure: By replacing min with logical OR and addition with logical AND, the algorithm computes reachability in directed graphs.
  • Network Routing: Used in distance-vector routing protocols to maintain global topology knowledge.
  • Game Theory & Optimization: Solves shortest-path formulations in Markov decision processes and network flow problems.
  • Compiler Design: Analyzes data-flow dependencies and constructs control-flow graphs during optimization passes.

Variations & Optimizations

Several adaptations extend the base algorithm's utility:

  • Path Reconstruction: Maintains a predecessor matrix next[i][j] to backtrack shortest paths in O(|V|) time per query.
  • Space-Optimized Version: Uses a single V × V matrix, sacrificing the ability to detect negative cycles without an additional pass.
  • Bit-Parallel Transitive Closure: Represents rows as bitsets, reducing the transitive closure to O(|V|³ / w), where w is the machine word size.
  • GPU Acceleration: Tile-based approaches on CUDA/OpenCL achieve throughput improvements of 15–30× for graphs with V > 1000[8].

See Also

Dijkstra's Algorithm

Single-source shortest paths, non-negative weights

Bellman–Ford Algorithm

Negative weight handling, cycle detection

Johnson's Algorithm

All-pairs for sparse graphs

Transitive Closure

Reachability in directed graphs

References

  1. Floyd, R. W. (1962). "Algorithm 97: Shortest Path". Communications of the ACM, 5(6), 345. doi:10.1145/368996.369025
  2. Warshall, S. (1962). "A Theorem on Boolean Matrices". Journal of the ACM, 9(1), 11–12.
  3. Ingerman, P. (1962). "Determination of the Transitive Closure of a Relation". Communications of the ACM, 5(1), 75. doi:10.1145/367639.367657
  4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. pp. 618–622.
  5. Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. §2.3.4.
  6. Dekel, E., et al. (1981). "Optimal Lower Bounds and Practical Parallel Algorithms for the Transitive Closure Problem". Journal of Computer and System Sciences, 22(2), 155–177.
  7. Srinivasa, R., et al. (2014). "GPU-Accelerated All-Pairs Shortest Path Algorithms". IEEE Transactions on Parallel and Distributed Systems, 25(9), 2341–2352.
  8. Aevum Encyclopedia Editorial Board. (2025). "Verification Methodology for Graph Algorithms". Aevum Technical Review, Vol. 12, Issue 3.