31,355 views

7 Answers

1 votes
1 votes

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

0 votes
0 votes
A min heap is required to implement it in linear time
0 votes
0 votes

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.

Answer:

Related questions

90 votes
90 votes
12 answers
1
44 votes
44 votes
4 answers
3
Rucha Shelke asked Sep 26, 2014
53,239 views
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?$\T...
39 votes
39 votes
4 answers
4
Rucha Shelke asked Sep 17, 2014
25,176 views
Which one of the following in place sorting algorithms needs the minimum number of swaps?Quick sortInsertion sortSelection sortHeap sort