search
Log In
1 vote
205 views

#plz check??

in Algorithms
edited by
205 views

1 Answer

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(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
0
@Habib what is meaning of invocation here
0
Just like we say number of invocation of function meaning that how many times the function is being called in main()..Same here..

Related questions

0 votes
0 answers
1
191 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?
asked Jan 6, 2019 in Algorithms Markzuck 191 views
0 votes
0 answers
3
293 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 how to solve such?
asked Dec 29, 2018 in Algorithms Markzuck 293 views
0 votes
0 answers
4
...