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

All-Pairs Shortest Paths Problem

Understanding the all-pairs shortest path problem and when it differs from single-source approaches.

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.