The Gateway to Computer Science Excellence
+1 vote
124 views

#plz check??

in Algorithms by Loyal (6.5k points)
edited by | 124 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..

by Veteran (102k points)
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..
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
198,316 comments
105,012 users