Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________

Category: QuestionsFloyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
Editor">Editor Staff asked 4 weeks ago

Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
 
(a) O(V*V)
 
(b) O(V*V*V)
 
(c) O(E*V)
 
(d) O(E*E)
 
This key question is from Directed Graph topic in section Graph of Data Structures & Algorithms I
 
The question was posed to me in examination.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right choice is (b) O(V*V*V)
 
The best explanation: The Algorithm uses Dynamic Programming and checks for every possible path.