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?

score 4 · Accepted Answer · answered Nov 14 '13 at 06:14

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

score 0 · Answer 2 · answered Mar 26 '14 at 09:10

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:

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

score -1 · Answer 3 · answered Nov 14 '13 at 05:51

-1

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

answered Nov 14 '13 at 05:51

Jamil Seaidoun

949
1
11
24

What parameters does decreaseKey take? – yw_maggie Nov 14 '13 at 05:57
Depends on your implementation but it should take at least the node or the index in the heap you want to decrease – Jamil Seaidoun Nov 14 '13 at 06:00
1

Link-only answers are not particularly appropriate for [so], not to mention that what you linked to **doesn't prove anything**, it just **claims** an O(log n) running time. – Bernhard Barker Nov 14 '13 at 07:05

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

3 Answers3