1
$\begingroup$

I have difficulties understanding how the priority queue is used in Dijkstra algorithm. Wikipedia lists 3 operations performed on priority queue:

  • add_with_priority(),
  • extract_min(),
  • decrease_priority().

With the first two I have no problems, both operations are screaming fast. But the last one is executed with the point at hand, not distance. So one has to first lookup the appropriate entry in the queue and if I am not mistaken you do this by simply iterating all elements (slow) or you use additional structure (associative array) which maps points into priority queue elements (but in total this won't be constant time).

So do I miss something or I can forget about constant time for decrease_priority (because it only applies from the moment when you have given entry already found)?

Sorry for not adding Dijsktra tag but I am with low rep here.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The data structure being used is a priority queue. $\endgroup$ – Yuval Filmus Dec 21 '18 at 18:34
  • 1
    $\begingroup$ You don't need to find the element. You can arrange to have a pointer at each edge which points at the correct entry of the priority queue. This pointer can be updated as elements move around in the queue. $\endgroup$ – Yuval Filmus Dec 21 '18 at 18:34
  • $\begingroup$ @YuvalFilmus, so I would work not with points per se, but I wound bind points (from map) + queue entries, and work with such pairs, so at any given time no lookup is needed. Looks good, thank you! :-) $\endgroup$ – greenoldman Dec 21 '18 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.