Vedkribhu's blog

Dijkstra's algorithm with using standard library for heap.
By Vedkribhu, history, 5 years ago, In English

I Dijkstra's algorithm we need to maintain heap for vertices who are not finalised. We need to modify the value of keys in the min heap. How can we do that without using custom heap written ourselves, but instead using Standard heap library like Heapq in python. I found this on stackoverflow but it is linear time to modify, can we do in logarithmic time complexity for decrease key? Any answer related to c++ or python will be awesome.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

When I implement Dijkstra using heap, I don't erase an old value. Instead, when I get a value from the heap, I check if it is actual.

In other words, I do something like this. Here d is the array of distances, q is the max heap with key {-d[v], v}

pair<int, int> p = q.top(); q.pop();
if (p.first != -d[p.second]) continue;

The fact that complexity is the same can be proven.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think, using make_heap() and pop_heap() instead of priority_queue<> can help.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In C++, if you want to modify heap element in logarithm time, there's more heaps in "policy based data structure" library but the constant seems to be big. Also you can use a set so you can erase the old element and insert the new element, which many people prefer to use.

→ Reply