@Habib what is meaning of invocation here

1 vote

Best answer

Let us see one by one :

One invocation (usage) of Dijkstra's Algo takes O(( |V| + |E| ) log V) time and we know |E| = O(V^{2}) ..So we can rewrite it as O( V^{2} log V) .. So V invocations will take O( V^{3} log V) which will be the complexity of finding all pair shortest path using Dijkstra's Algorithm.

Now coming to Bellman ford..For single source shortest path and hence single invocation we need O(VE) time = O(V^{3}) time..So for all pair shortest path we take V * O(V^{3}) = O(V^{4}) time..

Now coming to Floyd Warshalls algorithm we need O(V^{3}) time for the same problem of finding all pair shortest path..

**Hence 3) is the best option as it takes least time..**

**Hence D) is the correct answer..**