Why does decreasekey in Dijkstra's algorithm take O(logN) time?

Question

for the updating part,

for all neighbors w of u:
    if dist[w] > dist[u] + l(u,w)
        dist[w] = dist[u] + l(u,w)
        prev[w] = u
        decreasekey(H,w)

Here, w is the ID of the node, I think it should be like pair(ID,key) which key is the dist[ID]. If so, finding the node with ID w on a priority queue should cost O(N) time rather than O(logN) time. Then, why is decreasekey in Dijkstra's algorithm takes O(logN) time?

Answer 1

The heap implementation used for Dijktra is different from conventional priority queue implementation so inbuilt libraries of priority queue would not help you. The only solution is to implement your heap and keep track of position of each vertex in heap in an array. You need to update the pointers to vertex when u do insert or delete into heap. When u have to do decreaseKey in heap you have the direct location of vertex in heap and u can update the value of Key at that location . Use Heapify to reorder the heap (which takes O(logn)).

Answer 2

You are correct in saying that decrease key in a priority queue takes O(N) time. So to make the algorithm run in O(nlogn) time, you have one of these two options:

1. Implement a priority queue in which you will store the location of a node. This type of a priority queue supports deletion of a node in O(log n) time. You can find an implementation(in java) here. And dijkstra's algorithm code that uses this IndexMinPriorityQueue here.

2. Insert new values into the priority queue instead of decreaseKey operations. However worst case space usage will increase to O(M) while previously it was O(N), where M is the number of edges. You can verify that this algorithm will also work. In fact this is the method of choice in most applications where the number of edges in the graph is small and can fit in memory.

   for(all neighbors w of u){
       if (dist[w] > dist[u] + l(u,w)) {
           dist[w] = dist[u] + l(u,w);
           prev[w] = u;
           insert(H,w);
       }
   }
   

Answer 3

In a heap, decreaseKey takes O(logN) always. Proof