Search code examples
algorithmgraphstackqueuedijkstra

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

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

  • If the graph is unweighted, Dijkstra's algorithm is not needed. A simple BFS will work perfectly in O(E + V) time complexity, i.e. a linear time complexity.

    A simple implementation of the algorithm needs a queue data structure.