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.