in Algorithms
20,333 views
52 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
in Algorithms
20.3k views

6 Answers

63 votes
 
Best answer

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

edited by

15 Comments

if it is weighted graph then

min heap = mlogn

stack not used

queue not used ?

m i correct
2

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

5
@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.
15
wat is BFT ??
0
breadth first tree
0
breadth first traversal
3
Why is heap a wrong answer?

Or is there any reason why queue is more suitable?
2
Using heap the time complexity will be more as compared to BFS.
0

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.

0
BFS is not used to find shortest path in directed graph
0
edited by
@mohitrai0_0 relaxation and extract min both will still take log V time.
0

shashankpal

relaxation and extract min both will still take log V time.

why we even need. just tell me !!! that extract min will be used to extract minimum as unweighted graph so no cost and all that and no relaxation as well.

0

@ @

even after reading all the comments, I still didn’t get why are we only using queues but not stacks also. Can you please explain it?

 

0
edited by

Modified Algorithm:

intialize source and other vertex shortest paths – O(V)

Add source into Q(queue) -O(1)
s = null (set)
while Q != null: 

  1. u =deque(Q)
  2. s U {u} //set of shortest path vertices
  3. for all vertex(a) adjacent to u:
  4. if a not belongs to s
  5. relax (u,a,w) 
  6. add a to the queue

The total complexity is O(E) or no of edges, the same cant be implemented using stack since the shortest path cant be updated multiple times. Also it can be implemented in line time using stack.

correct me if i am wrong

0

@

here first of all the graph is unweighted so it indicates us to go for either bfs or dfs but as we know that to find the shortest path in any given graph we have to use bfs as dfs will not give the shortest path (it will only give any path which may not be the shortest one)  so as it is clear that we have to use bfs and bfs is implemented using queue ds… that’s why we are using queue instead of stack..

hope it is cleared now!

0
23 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

11 Comments

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
0
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
17
Why is BFS working correctly for unweighted graphs? That should say why DFS won't work.
1
sir if it is weighted the we use min heap . that take o(ElogV)
0
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).
2
yes, but until u know how dijkastra work,how do u conclude which data structure could use here?
1
@Sreshta if Dijikstra can run in linear time, then what is use of using BFS? i know how Dijikstra works
1
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.
16
perfect !!!
0

Using BFT SSSP can find in linear time. Hence Queue is correct option.
Even if all edges Weights are Positive and identical we can apply BFT to find single source shortest path in Graph which will take O(V+E) time.

0
In worst case E=O(V^2) , then how is this linear time?
0
3 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)

by
3 votes

I think none of the answers clearly explains why HEAP is not the correct answer here.

We know that we run “Extract_Min” total |V| time, hence (V logV), but as I see that many have argued that Extract_Min will take O(1) time only since all weights are same. But this is wrong. Had it been Kruskal’s MST algorithm then that argument would have been true. But here we don’t push edge weights in the heap, but rather the distance from the source to any particular vertex, and we know it need not be same for all vertex. And hence it will take O(log V) for both EXTARCT_MIN and RELAX functions.

And hence simple BFS implementation is the only way we can get linear runtime.

edited by

7 Comments

Bruh, can you please explain it in a bit more layman term..! Still can't figure out 😬
0
Both prim’s and Dijkstra are advanced versions of BFS. In other words, they are application of BFS.

Now when the weights are all one, why do we need this advanced version algorithm. We can simply run BFS once and it will give shortest paths to all the other nodes from the source node. And we know BFS needs queue.
2
Thank you bruh 🤗
0
In heap version of prims , don’t you first initialize every vertex.key with infinity ? there also heap wouldn’t be equivalent.
0

@ thanks. It will be same for Kruskal’s MST algorithm actually. Yea even for prim’s we push and modify key values in heap, so it won’t be the same.

0
But in kruskal don't we use union-find with path compression? Or you're saying that the part where we sort the edges, instead of sorting we should create a min heap?

And Also how to @ someone?
0
i follow normal Kruskal with heap, so will have to read about union-find method.

And i don’t think that tag @ works. It is just to direct question to a person, still, i just type ‘@’ and copy paste the link of the user.
0
1 vote

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.

 

this answer is in one of comment, bczz this is looking perfect and best answer that's why i am putting in answer by @srestha

0 votes
A min heap is required to implement it in linear time

5 Comments

Reason how min heap can implement it in linear time?
0
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).
2

@MiNiPanda

 

https://gateoverflow.in/891/gate2006-12?show=99143#c99143

 

Referring this, can you tell then why not heap ?

0
@HeadShot,

Firstly it says that all edges have same weight which is not right..it is an unweighted graph so no edge has any weight. We calculate the shortest path from source to a vertex based on the no. Of edges that fall in the shortest path.

Since no weight is given on what basis can we create a min heap and apply relax edges thereafter..?

If we apply edge weight 1 then for every iteration we need to check the adjacency list for that extracted node, relax edges and apply decrease-key operation whenever necessary. So this will not take constant time then.

Can you please elaborate the algorithm?

As far as I understand from the comment, since he says that extracting the min won't take logarithmic time that means whatever we replace the root with(for adjustment) we assume that the next min to be extracted will be this new one only. But what if this node is not connected to any of  the previously extracted ones?

Doesn't he consider relaxing the edges, updating the heap etc..?
0

@MiNiPanda

After reading your comment I realized something so here what I come to know please check : 

(and yeah thanx for your intuition it always helps:) )

And I think relaxation will work fine as after updating distance matrix we modify the heap ( as per me ).

And "membership" will work fine too as we have that array linked with our heap.

But yeah i am agree with you that it wont take constant time. ( as per me it may take vlogv )

bcoz its not like we are taking all the nodes and heapify. we gradually build the heap as per relaxation  so distance array will be changed gradually.

Please check the following : 

0
Answer:

Related questions