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?
- A.
O(n2logn)
- B.
Θ(n2logn)
- C.
Θ(n4)
- D.
Θ(n3)
Attempted by 107 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).