Which of the following algorithms solves the all-pairs shortest path problem?

Question

Accepted Answer

Correct answer: B — CONCEPT: The all-pairs shortest path (APSP) problem asks for the minimum-weight path between every pair of vertices in a weighted graph. Floyd's algorithm (the Floyd-Warshall algorithm) is the classical dynamic-programming solution to exactly this problem, computing all pairwise shortest distances in one O(V³) pass. APPLICATION — the DP recurrence, step by step: Initialize a distance matrix dist[i][j] with the direct edge weight between vertex i and vertex j (infinity if no direct edge exists, zero when i equals j). For each vertex k from 1 to V, treat k as a candidate intermediate vertex that a path could pass through. For every pair (i, j), update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) — check whether routing the path through k gives a shorter distance than the current best. After all V iterations of k are complete, dist[i][j] holds the true shortest distance between every pair of vertices — the complete all-pairs solution, in O(V³) time. CROSS-CHECK — what each algorithm actually computes: Algorithm What it actually computes Dijkstra's algorithm Shortest paths from one single source vertex to all others — a single-source result, not an all-pairs one — and only valid when every edge weight is non-negative. Running it once per vertex to assemble all-pairs distances (the idea behind Johnson's algorithm) is a separate composite technique; the algorithm itself is not classified as an all-pairs method. Floyd's algorithm Shortest paths between every pair of vertices, produced by the dynamic-programming recurrence above. Prim's algorithm A minimum spanning tree connecting all vertices at the least total edge weight — it produces no shortest-path distances at all. Warshall's algorithm The transitive closure of the graph — a boolean matrix of which vertex pairs are reachable at all — it ignores edge weights and produces no distances. RESULT: Only the recurrence above produces an actual shortest distance for every pair of vertices, so Floyd's algorithm is the one that solves the all-pairs shortest path problem.

Answer

A. Dijkstra's algorithm

Answer

B. Floyd's algorithm

Answer

C. Prim's algorithm

Answer

D. Warshall's algorithm

Algorithm	What it actually computes
Dijkstra's algorithm	Shortest paths from one single source vertex to all others — a single-source result, not an all-pairs one — and only valid when every edge weight is non-negative. Running it once per vertex to assemble all-pairs distances (the idea behind Johnson's algorithm) is a separate composite technique; the algorithm itself is not classified as an all-pairs method.
Floyd's algorithm	Shortest paths between every pair of vertices, produced by the dynamic-programming recurrence above.
Prim's algorithm	A minimum spanning tree connecting all vertices at the least total edge weight — it produces no shortest-path distances at all.
Warshall's algorithm	The transitive closure of the graph — a boolean matrix of which vertex pairs are reachable at all — it ignores edge weights and produces no distances.