Floyd-Warshall Time and Space Complexity
What you'll learn: You'll understand why Floyd-Warshall runs in O(V³) time and requires O(V²) space, and what this means for practical use.
Understanding the Time Complexity: O(V³)
Floyd-Warshall uses three nested loops, each iterating over all vertices in the graph. The outer loop chooses an intermediate vertex k, while the two inner loops examine every possible pair of vertices (i, j).
for k in range(V): # V iterations
for i in range(V): # V iterations
for j in range(V): # V iterations
# Constant-time relaxation operation
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Since we perform a constant-time operation (the min comparison) for each of V × V × V combinations, the total time complexity is O(V³).
Analogy: Imagine checking every possible route between all pairs of cities, considering each city as a potential layover point. With 100 cities, you'd make 100 × 100 × 100 = 1,000,000 checks.
Understanding the Space Complexity: O(V²)
Floyd-Warshall maintains a 2D distance matrix with dimensions V × V, storing the shortest distance between every pair of vertices. This gives us O(V²) space.
Unlike Dijkstra or Bellman-Ford (which track distances from a single source), Floyd-Warshall computes all-pairs distances, so the quadratic space requirement is inherent to the problem itself.
Note: The algorithm can update the matrix in-place, so no additional space proportional to V³ is needed despite the triple loop structure.
Key Takeaway: Floyd-Warshall's O(V³) time comes from three nested loops over all vertices, while its O(V²) space stores distances for all vertex pairs—making it efficient for dense graphs but costly for very large graphs.