GATE CSE 2006 | Question: 12

Question

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

• A. Queue
• B. Stack
• C. Heap
• D. B-Tree

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

 

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

Answer 2

A min heap is required to implement it in linear time

Comments

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

---

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

Answer 3

To implement Dijkstra's shortest path algorithm on unweighted graphs in linear time, the data structure to be used is a priority queue (often implemented as a binary heap).

The priority queue is used to store the nodes that have been visited and their distances from the source node. The algorithm repeatedly selects the node with the smallest distance from the source node from the priority queue and updates the distances of its neighboring nodes. The priority queue allows for efficient access to the node with the smallest distance, which is crucial for maintaining the linear time complexity of the algorithm.

Alternatively, we can use a data structure called Fibonacci Heap which performs better than binary heap in terms of time complexity.