min heap = mlogn

stack not used

queue not used ?

m i correct

Rucha Shelke
asked
in Algorithms
Sep 16, 2014

20,333 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:

- Queue
- Stack
- Heap
- B-Tree

Best answer

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

edited
Sep 4
by solaikannan

Modified Algorithm:

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

Add source into Q(queue) -O(1)

s = null (set)

while Q != null:

- u =deque(Q)
- s U {u} //set of shortest path vertices
- for all vertex(a) adjacent to u:
- if a not belongs to s
- relax (u,a,w)
- 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

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

hope it is cleared now!

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

Reference: geekforgeeks

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

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

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.

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.

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.

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.

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.

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

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

@MiNiPanda

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

Referring this, can you tell then why not heap ?

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

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

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

Search GATE Overflow