Made Easy Test Series

Question

Which of the following can be the best algorithm(s) for all pair of the shortest path problem?

I. ‘V’ invocations of Dijkstra algorithm ⇒ Ο(VE logV).
II. ‘V’ invocations of Bellman-Ford algorithm ⇒ Ο(V2 E).
III. ‘1’ invocations of Floyd-Warshall algorithm ⇒ Ο(V3).

Answer 1

I think answer should be only III i.e. ‘1’ invocations of Floyd-Warshall algorithm ⇒ Ο(V3).

Reason for saying this –

As we know for complete graph number of edges , E = V(V-1)/2 nearly equal to V^2 , so for complete graph

I.‘V’ invocations of Dijkstra algorithm ⇒ Ο(VE logV) becomes O(V^3logV)

II. ‘V’ invocations of Bellman-Ford algorithm ⇒ Ο(V2 E) becomes O(V^4)

III. ‘1’ invocations of Floyd-Warshall algorithm ⇒ Ο(V3) remains O(V^3) only.

Hence considering best cases for all types of graph one must prefer option III 

 

Answer 2

Only III should be the answer because in the worst case(i.e. complete graph) Floyd-Warshall performs better than any other algorithms which exist right now.