edited by
727 views

1 Answer

Best answer
1 votes
1 votes

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(V2) ..So we can rewrite it as O( V2 log V) .. So V invocations will take O( V3 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(V3) time..So for all pair shortest path we take V * O(V3)  =  O(V4) time..

Now coming to Floyd Warshalls algorithm we need O(V3) 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..

selected by

Related questions

1 votes
1 votes
1 answer
1
Markzuck asked Jan 6, 2019
491 views
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
0 votes
0 votes
1 answer
2
Markzuck asked Dec 29, 2018
775 views
cant we write the recurrance relation for bar() as T(n) = 5T(n-1) + c,like cant we take both the recurrance call as combined as both have same parameter?and if not, then ...
1 votes
1 votes
0 answers
3
1 votes
1 votes
1 answer
4