Hello guys,

I'm implementing Dijkstra and I have a question regarding the priority queues. Most people use one of the STL queues to store their list of nodes to be visited. However it seems that these queues (std::set, std::make_queue, etc) don't allow to store two or more nodes that have the same exact distance to the start node.

Take this example:

Start Node-----3-----Node1

|

3

|

Node2

As you can seen both Node1 and Node2 have the same distance of 3 to the start node so when exploring the start node you would insert both Node1 and Node2 into the queue. However the insertion of the second node will fail because the priority queue already has a node with shortest distance = 3. Can someone confirm this observation is true?

I've seen my implementation fail to find the shortest path because of this fact. It is a rare phenomenon because it is not probable that two nodes have the exact same distance but it does happen and when it does the algorithm fails completely.

Thanks in advance

I typically use a std::vector and the heap functions (std::make_heap, std::sort_heap, std::push_heap, and std::pop_heap) to implement a priority queue for Dijkstra's algorithm.

Thank you all for your answers, things are getting clearer now.

Use a std::priority_queue.

I've tried it and it works fine, thank you! There is one more issue though, imagine this:

- Node1 is already in the queue with a shortest cost of 3

- During the graph exploration I find a new shortest path to Node1 with cost 2

- So I insert Node1 into the queue with the new cost of 2

Won't this create a duplicate entry of Node1 on the queue, where the first entry as a cost of 3 and the second entry has a cost of 2?

Is there an easy way to update the existing entry on the queue and re-sort the queue?

I've tried it and it works fine, thank you! There is one more issue though, imagine this:
- Node1 is already in the queue with a shortest cost of 3
- During the graph exploration I find a new shortest path to Node1 with cost 2
- So I insert Node1 into the queue with the new cost of 2

Won't this create a duplicate entry of Node1 on the queue, where the first entry as a cost of 3 and the second entry has a cost of 2?
Is there an easy way to update the existing entry on the queue and re-sort the queue?

If you don't want duplicates in your priority queue, you'll have to write your own so you can update an existing element. Priority queues are actually pretty easy to write.

Many thanks, I followed your advice and implemented a binary heap myself and I got nice results. My custom heap allows to update existing items which is very convenient for pathfinding and gives a big performance boost in comparison to STL containers which cannot update items (forcing me to remove items and re-insert items just to re-sort them).

I definitely recommend using a custom well implemented priority queue for pathfinding if performance is important.