Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is a dynamic programming algorithm that computes the shortest paths between all pairs of vertices in a weighted directed graph, including graphs with negative edge weights (but no negative cycles). It systematically improves an estimate of the shortest path between every pair of vertices by considering each vertex as an intermediate node. With a time complexity of O(V³) and space complexity of O(V²), it is widely used in network routing, transitive closure computation, and geographic information systems.
Key Formula
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
LaTeX: d^{(k)}[i][j] = \min\bigl(d^{(k-1)}[i][j],\; d^{(k-1)}[i][k] + d^{(k-1)}[k][j]\bigr)
| Symbol | Meaning | Unit |
|---|---|---|
| d^{(k)}[i][j] | Shortest distance from vertex i to j using vertices 1..k as intermediates | weight units |
| k | Current intermediate vertex index | dimensionless |
| i, j | Source and destination vertex indices | dimensionless |
Worked Example
Problem
Given a graph with 4 vertices and edges: (1→2, w=3), (1→3, w=8), (1→4, w=-4), (2→4, w=7), (2→3, w=4), (3→2, w=-5), (4→3, w=2), find the shortest path from vertex 1 to vertex 3.
Solution
Step 1: Initialise dist matrix from edge weights; dist[1][1]=0, dist[1][2]=3, dist[1][3]=8, dist[1][4]=-4; inf elsewhere. Step 2: k=1 — route through vertex 1; no improvements over direct edges. Step 3: k=2 — dist[1][3] = min(8, dist[1][2]+dist[2][3]) = min(8, 3+4) = 7; dist[1][4] = min(-4, 3+7) = -4. Step 4: k=3 — dist[3][2] = -5 enables dist[1][2] = min(3, 7+(-5)) = 2; dist[1][4] = min(-4, 7+inf) = -4. Step 5: k=4 — dist[1][3] = min(7, -4+2) = -2.
Answer
Shortest path from vertex 1 to vertex 3 = -2 (via 1→4→3)
Floyd-Warshall vs Other All-Pairs Shortest Path Algorithms
| Algorithm | Time Complexity | Space Complexity | Handles Negative Weights | Best Use Case |
|---|---|---|---|---|
| Floyd-Warshall | O(V³) | O(V²) | Yes (no negative cycles) | Dense graphs, all-pairs |
| Johnson's Algorithm | O(V² log V + VE) | O(V²) | Yes (no negative cycles) | Sparse graphs, all-pairs |
| Dijkstra (repeated) | O(V² log V + VE) | O(V) | No | Non-negative weights |
| Bellman-Ford (repeated) | O(V²E) | O(V) | Yes | Single-source, negative weights |
| BFS (unweighted) | O(V(V+E)) | O(V) | N/A | Unweighted graphs |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Named after Robert W. Floyd who published the algorithm in 1962 and Stephen Warshall who described a related algorithm for transitive closure in 1962. The name combines both contributors' surnames. Floyd derived the algorithm from Bernard Roy's 1959 work on transitive closure.