GATE 2007
March 20, 2025GATE 2007
March 20, 2025GATE 2007
|
Question 41
|
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
|
Dijkstra’s algorithm starting from S.
|
|
|
Warshall’s algorithm.
|
|
|
Performing a DFS starting from S.
|
|
|
Performing a BFS starting from S.
|
Question 41 Explanation:
→ Time Complexity of the Dijkstra’s algorithm : It depends on your implementation of Dijkstra’s Algorithm. Simple algorithm is given below with Time complexity of O(V2). There are also some time-efficient Algorithms: Graph represented using adjacency list can be reduced to O(E log V) with the help of binary heap.
→ Time Complexity of the Warshall’s algorithm: O(n3). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)
→ Time Complexity of the Warshall’s algorithm: O(n3). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)
Correct Answer: D
Question 41 Explanation:
→ Time Complexity of the Dijkstra’s algorithm : It depends on your implementation of Dijkstra’s Algorithm. Simple algorithm is given below with Time complexity of O(V2). There are also some time-efficient Algorithms: Graph represented using adjacency list can be reduced to O(E log V) with the help of binary heap.
→ Time Complexity of the Warshall’s algorithm: O(n3). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)
→ Time Complexity of the Warshall’s algorithm: O(n3). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)