Блог пользователя Vedkribhu

Dijkstra's algorithm with using standard library for heap.
Автор Vedkribhu, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить