Dark Mode

190 views

3 votes

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