6k 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

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
+2
if it is weighted graph then

min heap = mlogn

stack not used

queue not used ?

m i correct
+2

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

+8
@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.
0
wat is BFT ??
0
+2
+1
Why is heap a wrong answer?

Or is there any reason why queue is more suitable?
0
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.

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

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)

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

@MiNiPanda

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

Referring this, can you tell then why not heap ?

0

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

2