CODEWITHSUNDEEP
algorithmheappriority-queuedijkstradecrease-key
yw_maggie
yw_maggie

Reputation: 53

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

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?

Upvotes: 4

Views: 1511

Answers (3)

Vikram Bhat
Vikram Bhat

Reputation: 6246

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 you do insert or delete into heap. When you have to do decreaseKey in heap you have the direct location of vertex in heap and you can update the value of Key at that location . Use Heapify to reorder the heap (which takes O(log n)).

Upvotes: 5

Nikunj Banka
Nikunj Banka

Reputation: 11385

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);
    }
}

Upvotes: 1

Jamil Seaidoun
Jamil Seaidoun

Reputation: 969

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

Upvotes: -1

Related Questions