Register

GATE Overflow Test Series | Algorithms | Test 2 | Question: 5

283 views
5 votes
5 votes

Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph where all edge weights are equal?

  1. Dijkstra's algorithm
  2. Bellman-Ford algorithm
  3. Topological Sort
  4. Prim's algorithm
User Avatar

1 Answer

Best answer
5 votes
5 votes
For a Directed Acyclic Graph Topological Sort can be done to find the shortest path in $\Theta(|V| + |E|)$ time which is better than the time complexities of Dijkstra's $(O(|V| \lg |V| + E)$ best known implementation with Fibonacci heap) and Bellman-Ford $(O(VE))$ .
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
1 answer
3
gatecse asked Sep 7, 2020
188 views
GATE Overflow Test Series | Algorithms | Test 2 | Question: 6
Given a directed graph where weight of every edge is same, we can efficiently find the shortest path from a given source to destination using _____ Breadth First Traversal Dijkstra's Shortest Path Algorithm Bellman-Ford Algorithm Depth First Search
Given a directed graph where weight of every edge is same, we can efficiently find the shortest path from a given source to destination using _____Breadth First Traversal...
User Avatar
4 votes
4 votes
1 answer
4
gatecse asked Sep 7, 2020
266 views
GATE Overflow Test Series | Algorithms | Test 2 | Question: 18
Which of the following statements is/are TRUE with respect to the time complexities of the graph algorithms to find Single Source Shortest Path (SSSP)? (Mark all the appropriate choices) Bellman-Ford algorithm to find SSSP runs in $O(VE)$ Dijkstra ... $O(|V|+|E|)$
Which of the following statements is/are TRUE with respect to the time complexities of the graph algorithms to find Single Source Shortest Path (SSSP)? (Mark all the appr...
User Avatar
Link Copied!