Which of the following algorithms solves the all-pairs shortest path problem?
2018
Which of the following algorithms solves the all-pairs shortest path problem?
Answer: B. Floyd’s algorithm — The all-pairs shortest path problem is solved by Floyd’s algorithm (Floyd–Warshall algorithm) , which computes shortest paths between every pair of vertices…
- A.
Dijkstra’s algorithm
- B.
Floyd’s algorithm
- C.
Prim’s algorithm
- D.
Warshall’s algorithm
Attempted by 505 students.
Show answer & explanation
Correct answer: B
The all-pairs shortest path problem is solved by Floyd’s algorithm (Floyd–Warshall algorithm) , which computes shortest paths between every pair of vertices using dynamic programming. Dijkstra’s algorithm → single-source shortest path
Prim’s algorithm → minimum spanning tree
Warshall’s algorithm → transitive closure
Loading lesson…