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

3
votes

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?

1
algorithmgraphstackqueuedijkstra
You first answer is not even related to Dijkstra's algorithm. – Rasul Kerimov
@RasulKerimov for unweighted graphs, Dijkstra's algorithm reduces to BFS, so (1) is essentially correct. (2) is just wrong. – Matt Timmermans
I don't get it. How Dijkstra can reduce to BFS. Two different approaches. – Rasul Kerimov
@MattTimmermans so option (A) is correct and rest all are false? – Nivedita
@RasulKerimov every new node discovered will have its initial priority set >= all the priority of all previously discovered nodes, and it will never need to be adjusted. Nodes can therefore be processed in FIFO order using a queue of discovered nodes, which turns it into BFS – Matt Timmermans

1 Answers

11
votes

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 .