To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, which data structure should be used?

Question

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

1. Queue
2. Stack
3. Heap
4. B-Tree

I found below answers:

1. A Queue because we can find single source shortest path in unweighted graph by using Breadth first search (BFS) algorithm which using "Queue" data structure , which time O(m+n) (i.e. linear with respect to the number of vertices and edges. )

2. A min heap is required to implement it in linear time because if we delete here a node in min heap it will not take any time in adjustment because all r having same weight so deletion will take O(1) for one node .. so for n-1 node it will be O(n).

Can someone explain which one is the correct answer?

Solution

please note that if the graph is unweighted no dijekstra is needed a simple BFS will work perfectly in O(E + V) ==> linear Time A simple implementation of the algorithm needs A Queue Data Structure .