To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
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. )
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???
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.
Ans Can Also be (C) Heap.
Min Heap Creation Time O(V)
Deletion From Heap Constant Time(Because All elements are Equal)
Visiting Adj. List time O(E)
So total is O(V+E)
Referring this, can you tell then why not heap ?
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 :
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
Hi I have made the payment on June...