3.5k 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 which using "Queue" data structure , which time $O(m+n)$ (i.e. linear with respect to the number of vertices and edges. )

edited by
+2
if it is weighted graph then

min heap = mlogn

stack not used

queue not used ?

m i correct
+1

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.
0
wat is BFT ??
0
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
+7
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
+7
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?
+1
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).