Course contentsShow
← Computer Science
Lesson 999 of 2,87223. Shortest Path AlgorithmsFree lesson

Floyd-Warshall vs Repeated Dijkstra

Comparing when to use Floyd-Warshall versus running Dijkstra V times for all-pairs problems.

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.