3.7All-pairs shortest paths and reachability
The idea
Floyd-Warshall computes shortest paths between all pairs with three nested loops, allowing negative edges.
Think of it like this: Allowing one more stopover city at a time and checking whether it shortens any trip.
Why it exists
Its Θ(V³) cost and the loop order are standard questions.
How it works
- d[i][j] starts as the direct edge weight (∞ if none).
- For each intermediate vertex k:
- for every pair (i, j): d[i][j] = min(d[i][j], d[i][k] + d[k][j]).
- The same loops with OR/AND give the transitive closure.
Worked example: V = 100
Floyd-Warshall costs about 10⁶ steps. Dijkstra from every vertex on a sparse graph costs about 100 × (100 + E) log 100.
Now play with it
- →Read the table that picks an algorithm per situation.
- →Note which ones allow negative edges.
| Problem | Algorithm | Time |
|---|---|---|
| All pairs, negative edges allowed | Floyd-Warshall | Θ(V³) |
| All pairs, sparse, non-negative | Dijkstra from every vertex | O(V(V + E) log V) |
| Transitive closure | Warshall (OR / AND) | Θ(V³) |
| Single source, negative edges | Bellman-Ford | O(VE) |
| Single source, non-negative | Dijkstra (heap) | O((V + E) log V) |
Floyd-Warshall: for k, for i, for j: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). After round k, d uses only intermediate vertices 1..k.
Check yourself
The running time of Floyd-Warshall on V vertices is
Exam notes (the dense version)
Floyd-Warshall: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for k = 1..V, three nested loops, Θ(V³), handles negative edges but not negative cycles. Running Dijkstra from every vertex costs O(V(V + E) log V). The same triple loop with OR and AND computes the transitive closure (Warshall).
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.