To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Answer is A: Queue
We can find single source shortest path in unweighted graph by using Breadth First Search (BFS) algorithm by using "Queue" data structure , in time $O(m+n)$ (i.e. linear with respect to the number of vertices and edges. )
for this ques why cant we use stack becz using BFS and DFS both we can get complexity of linear time . So why we are only biasing towards BFS .Pls explain???
no it won't be, it will run in O(V+E) as well, deletion from the heap won't take logarithmic time but constant as all elements are same.
Ans Can Also be (C) Heap.
Min Heap Creation Time O(V)
Deletion From Heap Constant Time(Because All elements are Equal)
Visiting Adj. List time O(E)
So total is O(V+E)