All-Pairs Shortest Paths Problem
What you'll learn: You'll understand what the all-pairs shortest path problem is and when you need it instead of single-source approaches.
What is the All-Pairs Shortest Paths Problem?
So far, we've explored single-source shortest path algorithms like Dijkstra's and Bellman-Ford. These find the shortest paths from one starting vertex to all other vertices in a graph.
But what if you need to know the shortest path between every pair of vertices? That's the all-pairs shortest paths (APSP) problem: given a graph with V vertices, find the shortest distance between all V × V possible pairs.
When Single-Source Isn't Enough
Think of it like this: Single-source is like standing at one city and mapping routes to every other city. All-pairs is like creating a complete distance table for every city to every other city.
You encounter APSP when:
- Building routing tables for entire networks
- Analyzing graph connectivity metrics (diameter, centrality)
- Preprocessing distance queries in navigation systems
- Computing transitive closures
Naive Approach vs Specialized Algorithms
You could solve APSP by running Dijkstra's or Bellman-Ford V times (once per source vertex). This works but may not be optimal:
- V × Dijkstra's: O(V³) with binary heap on dense graphs
- V × Bellman-Ford: O(V⁴) time
However, specialized all-pairs algorithms can leverage the structure of computing all distances simultaneously to potentially achieve better complexity or simplicity—something we'll explore in upcoming lessons.
Key Takeaway: The all-pairs shortest paths problem finds shortest distances between every pair of vertices, not just from one source. While you can run single-source algorithms V times, specialized approaches often provide better solutions for this comprehensive distance computation.