What is the All-Pairs Shortest Path Problem?
Learn all-pairs shortest path, how Floyd-Warshall works, and when to use it over repeated Dijkstra for this graph interview question.
Expected Interview Answer
All-pairs shortest path (APSP) computes the minimum-cost route between every pair of vertices in a graph at once, typically solved with the Floyd-Warshall algorithm in O(V³) time using dynamic programming, or by running Dijkstra from every vertex when the graph is sparse and weights are non-negative.
Floyd-Warshall builds a V-by-V distance matrix and iteratively considers every vertex k as a possible intermediate stop, updating dist[i][j] to min(dist[i][j], dist[i][k] + dist[k][j]) for every pair (i, j). After all V iterations, the matrix holds every pair's shortest distance, and it naturally handles negative edges as long as there is no negative cycle, which shows up as a negative value on the diagonal. The alternative, running Dijkstra from each of the V vertices, costs O(V * (V + E) log V), which is faster than Floyd-Warshall on sparse graphs but requires non-negative weights. The choice hinges on graph density: dense graphs favor Floyd-Warshall's simplicity, sparse graphs favor repeated Dijkstra (Johnson's algorithm reweights edges to make this work even with negative weights).
- Answers any pair query in O(1) after preprocessing
- Floyd-Warshall handles negative weights (no negative cycles)
- Simple triple-nested-loop implementation
- Diagonal check doubles as negative-cycle detection
AI Mentor Explanation
All-pairs shortest path is like a league statistician precomputing the fastest relay-throw time between every single pair of fielding positions on the ground, not just from one position. Rather than recalculating from scratch for each pair, the statistician tries every position k as a possible relay stop, checking whether bouncing the ball through k beats the current best-known time between any two positions i and j. After trying every possible relay stop, the table holds the fastest time between all position pairs at once. This is exactly Floyd-Warshall's triple loop — treat every position as a potential shortcut, once each, for every pair.
Step-by-Step Explanation
Step 1
Build the initial distance matrix
dist[i][j] = edge weight if an edge exists, 0 on the diagonal, infinity otherwise.
Step 2
Iterate over every intermediate vertex k
For each k from 1 to V, consider it as a possible waypoint between every pair (i, j).
Step 3
Relax through the intermediate vertex
Update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every pair.
Step 4
Check the diagonal for negative cycles
If any dist[i][i] becomes negative after all iterations, the graph contains a negative cycle.
What Interviewer Expects
- State Floyd-Warshall's O(V³) time and O(V²) space
- Explain the intermediate-vertex relaxation clearly
- Compare against running Dijkstra V times for sparse graphs
- Know Floyd-Warshall detects negative cycles via the diagonal
Common Mistakes
- Forgetting the intermediate vertex loop must be the outermost loop
- Using Floyd-Warshall on huge sparse graphs where repeated Dijkstra is faster
- Not initializing dist[i][i] to 0 before running the algorithm
- Assuming Floyd-Warshall works with a negative cycle present (it does not give valid distances)
Best Answer (HR Friendly)
“All-pairs shortest path answers: what is the cheapest way to get between every possible pair of points in the network, all at once? I would reach for Floyd-Warshall's dynamic-programming approach on a dense graph, or run Dijkstra from every node if the graph is large and sparse.”
Code Example
def floyd_warshall(num_vertices, edges):
INF = float("inf")
dist = [[INF] * num_vertices for _ in range(num_vertices)]
for i in range(num_vertices):
dist[i][i] = 0
for u, v, weight in edges:
dist[u][v] = min(dist[u][v], weight)
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
has_negative_cycle = any(dist[i][i] < 0 for i in range(num_vertices))
return dist, has_negative_cycleFollow-up Questions
- When would you prefer running Dijkstra V times over Floyd-Warshall?
- How does Johnson's algorithm combine Bellman-Ford and Dijkstra for APSP?
- How would you reconstruct the actual path, not just the distance, from Floyd-Warshall?
- What happens to Floyd-Warshall's output if the graph has a negative cycle?
MCQ Practice
1. What is the time complexity of the Floyd-Warshall algorithm?
Floyd-Warshall uses three nested loops over all vertices, giving O(V³) time.
2. In Floyd-Warshall, what does a negative value on the distance matrix diagonal after completion indicate?
dist[i][i] should stay 0; a negative value means a cycle through i reduces cost indefinitely, i.e. a negative cycle.
3. For a sparse graph with non-negative weights, which approach is typically faster for all-pairs shortest paths?
Running Dijkstra V times costs O(V * (V + E) log V), which beats O(V³) Floyd-Warshall when E is much smaller than V².
Flash Cards
What does APSP compute? — The shortest distance between every pair of vertices in the graph, all at once.
What is Floyd-Warshall's time complexity? — O(V³), using dynamic programming over intermediate vertices.
What is the Floyd-Warshall relaxation rule? — dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every intermediate k.
When is repeated Dijkstra preferred over Floyd-Warshall? — On large sparse graphs with non-negative weights, since O(V(V+E)logV) beats O(V³).