The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
3.2k views

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
asked in Algorithms by Loyal (4.3k points) | 3.2k views

4 Answers

+37 votes
Best answer

Answer is A: Queue

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. )

answered by Boss (5.9k points)
edited by
if it is weighted graph then

min heap = mlogn

stack not used

queue not used ?

m i correct

@Mithlesh Upadhyay


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???

@Aditi Tiwari It's not just about the time complexity. BFS is used as it helps to find single source shortest path for unweighted graph. For eg- all nodes directly connected to root are at a shortest distance 1, nodes at 2nd level in BFT tree are at shortest distance of 2 from the root and so on.  But DFS can't be used to do so.
wat is BFT ??
breadth first tree
+12 votes
Answer(A) The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths

Reference: geekforgeeks
answered by Veteran (81k points)
why we not use stack. if dfs also take o(n+m) time. and if it is weighted then we use min heap . am i right
What I think DFS could not work here. because DFS goes in max deph of each path.

It cannot find shortest path in each turn.

But in BFS it traverse each direction at the same time.

When it get shortest , it no need to wait for other path, And it automatically stops there,

that is it is FIFO. And FIFO is only performed in queue
Why is BFS working correctly for unweighted graphs? That should say why DFS won't work.
sir if it is weighted the we use min heap . that take o(ElogV)
I have got only one question here, We should discuss about Dijikstra not BFS, because question is asked about the implementation of Dijikstra, right?
That's a different thing that BFS can do it in O(m=n).
yes, but until u know how dijkastra work,how do u conclude which data structure could use here?
@Sreshta if Dijikstra can run in linear time, then what is use of using BFS? i know how Dijikstra works
See, they want to know dijkastra works for linear time(O(N) time, where N is no. of vertex.)

In general dijkastra works in O(E+Nlog N)

Now, we have to think about a data structure which work for dijkastra in O(N) time.

Now, it can be array, stack, queue. Which one suitable?

We have to go each path and in each turn we have to find shortest path. This is nothing but BFS. And BFS works for Queue. So, answer queue here.
perfect !!!
+2 votes

Ans Can Also be (C) Heap.

  1. Min Heap Creation Time O(V)

  2. Deletion From Heap Constant Time(Because All elements are Equal)

  3. Visiting Adj. List time O(E)

So total is O(V+E)

answered by (151 points)
0 votes
A min heap is required to implement it in linear time
answered by Veteran (14.3k points)
Reason how min heap can implement it in linear time?
Bcz if we delete here  a node in min heap it will not take any time in adjustment bcz all r having same weight so deletion will take o(1) for one node .. so for n-1 node it will be o(n).


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
114,021 comments
38,389 users