GATE 2001
April 6, 2025GATE 2006
April 6, 2025GATE 2006
| Question 12 |
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
| Queue | |
| Stack | |
| Heap | |
| B-Tree |
Question 12 Explanation:
Queue: Basically we do BFS-traversal of the graph to get the shortest paths. There is no point of using Min-heap if it is unweighted graph. Even though if you use after every extract min operation you have to do min-heapify which takes O(log V) time. so, the total time will be O(VlogV). As it is undirected graph you should do BFS from the source then you will get shortest path only. It will take O(V+E) time.
Correct Answer: A
Question 12 Explanation:
Queue: Basically we do BFS-traversal of the graph to get the shortest paths. There is no point of using Min-heap if it is unweighted graph. Even though if you use after every extract min operation you have to do min-heapify which takes O(log V) time. so, the total time will be O(VlogV). As it is undirected graph you should do BFS from the source then you will get shortest path only. It will take O(V+E) time.