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?
- A.
Dijkstra’s algorithm
- B.
Floyd’s algorithm
- C.
Prim’s algorithm
- D.
Warshall’s algorithm
Attempted by 575 students.
Show answer & explanation
Correct answer: B
Floyd’s algorithm (Floyd–Warshall) computes the shortest paths between all pairs of vertices in a weighted graph. Key points: Purpose: Computes shortest-path distances for every ordered pair of vertices (all-pairs shortest paths).