Which of the following is the best-case time complexity of Floyd’s algorithm…
2017
Which of the following is the best-case time complexity of Floyd’s algorithm for finding shortest paths in a graph with ‘n’ vertices?
- A.
Θ(n²)
- B.
Θ(1)
- C.
Θ(n)
- D.
Θ(n³)
Attempted by 152 students.
Show answer & explanation
Correct answer: D
The Floyd-Warshall algorithm computes all-pairs shortest paths using a dynamic programming approach. It strictly executes three nested loops running from 1 to n, regardless of the graph's structure, edge weights, or density. Therefore, its best-case, average-case, and worst-case time complexities are all identical at Θ(n3).
Thus, the correct option is D.