Floyd-Warshall vs Repeated Dijkstra
You'll learn when to choose Floyd-Warshall versus running Dijkstra V times for solving all-pairs shortest paths.
Both approaches solve the all-pairs shortest paths problem—finding shortest paths between every pair of vertices—but they shine in different scenarios.
The Core Tradeoff
Floyd-Warshall computes all-pairs paths in one pass with O(V³) time and O(V²) space. It's straightforward: three nested loops checking if routing through intermediate vertices shortens paths.
Repeated Dijkstra runs Dijkstra from each vertex. With a binary heap, this takes O(V · (E log V)) = O(VE log V) time. With a Fibonacci heap, it's O(V² log V + VE).
When to Choose Each
Use Floyd-Warshall when:
- Your graph is dense (many edges, approaching E ≈ V²). Here O(V³) and O(V²E) are similar.
- The graph has negative edge weights (but no negative cycles). Dijkstra can't handle these.
- You want simpler implementation—no priority queues needed.
- V is small enough that O(V³) is acceptable.
Use Repeated Dijkstra when:
- Your graph is sparse (E << V²). For example, if E = O(V), repeated Dijkstra takes O(V² log V), much better than O(V³).
- All edges are non-negative. This is Dijkstra's domain.
- You can leverage Fibonacci heaps for better asymptotic performance.
- You might not need all pairs—you can stop early.
Practical Example
For a dense graph with 1000 vertices and 500,000 edges (halfway to complete): Floyd-Warshall does ~1 billion operations. Repeated Dijkstra with binary heap does ~500,000 × 1000 × log(1000) ≈ 5 billion operations. Floyd-Warshall wins.
For a sparse graph with 1000 vertices and 2000 edges: Floyd-Warshall still does ~1 billion operations. Repeated Dijkstra does ~2000 × 1000 × log(1000) ≈ 20 million operations. Dijkstra wins decisively.
Key Takeaway: Choose Floyd-Warshall for dense graphs or negative weights; choose repeated Dijkstra for sparse graphs with non-negative edges.