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)