Dijkstra's algorithm - how could a priority queue or min-heap be used?

Question

I've been struggling implementing Dijkstra's algorithm; more specifically the part with the priority queue. To add vertices into a data structure and use an iterator to go through all vertices and find the minimum distance; that would be easy, but n time.

What I want is to:

• to be able to insert vertices into the data structure
• extract (return and remove) the vertex v with the lowest distance dist[v]

I believe that for Dijkstra's algorithm to work properly, you should be able to insert vertices in constant time and extract them in log(n) time; and I've been suggested that priority queues and min-heaps could be used, but to me it doesn't seem realistic that we could keep the queue or min-heaps ordered, because the distances are getting constantly modified.

So how am I supposed to declare and use a priority queue, a min-heap or another data structure to do this?

Answer 1

You can use a pair to store the node along with the value (the first element should be the value so that the priority queue compares with this value). Maintain a boolean array visit [ ] where you will indicate wheather you have visited or not a certain node (intially all false).

Every time you take the front element of the priority queue check if you have visited this node that is check if visit[pq.front().second] == false. Check for all its adjacent edges and add the nodes reached from this path. If it is true then you should ignore it, as you have already visited it with less length. You will not add more than E edges so the time complexity remains the same.

You can learn more about this approach in this link http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#priority.

Answer 2

You have basically three choices here:

1. Use a tree or some other DS that allows you to extract arbitrary number in O(logN). A heap cannot provide this behavior.
2. Maintain an additional DS (could be hash based) that maps map:V->Node Reference - this will allow you to find the desired node efficiently in the heap, and removing a node where you know its position is doable in O(logN) in the heap (the problem is the finding...)
3. "Insert anyway", ignore the fact that the heap already contains this node. It will cause you to have a larger heap, at size O(n^2) worst case (number of edges), but recall that log(N^2)=2log(N) which is in O(logN)