@Habib what is meaning of invocation here

The Gateway to Computer Science Excellence

+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..**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,306 answers

198,316 comments

105,012 users