Which of the following algorithm solves the all-pair shortest path problem?
2017
Which of the following algorithm solves the all-pair shortest path problem?
- A.
Prim’s algorithm
- B.
Dijikstra’s algorithm
- C.
Bellman-Ford’s algorithm
- D.
Floyd-Warshall’s algorithm
Attempted by 261 students.
Show answer & explanation
Correct answer: D
The All-Pair Shortest Path problem requires finding the shortest path between every pair of vertices in a graph. Floyd-Warshall’s algorithm is specifically designed for this task, dynamically computing shortest paths between all pairs of nodes. In contrast, Prim’s algorithm is used for Minimum Spanning Trees, while Dijkstra’s and Bellman-Ford algorithms are designed for Single-Source Shortest Path problems.