What is the time complexity of the Floyd-Warshall algorithm to calculate all…
2023
What is the time complexity of the Floyd-Warshall algorithm to calculate all the shortest paths of a pair in an n-vertex graph?
Answer: D. Θ(n3) — The Floyd – Warshall algorithm uses three nested loops to calculate all the shortest paths. Therefore, the time complexity is Θ(n ^ 3).
- A.
O(n2logn)
- B.
Θ(n2logn)
- C.
Θ(n4)
- D.
Θ(n3)
Attempted by 265 students.
Show answer & explanation
Correct answer: D
The Floyd – Warshall algorithm uses three nested loops to calculate all the shortest paths. Therefore, the time complexity is Θ(n ^ 3).
Loading lesson…