Sign in to follow this  
jcabeleira

Dijsktra and STL Priority Queues

Recommended Posts

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

Edited by jcabeleira

Share this post


Link to post
Share on other sites
If you use a std::set as your data structure then it will fail when you try to add a second element with the same distance because a std::set expects unique elements.

While it may be tempting to use a std::set because it gives you an ordering like a priority queue it isn't the same thing because a priory queue can have multiple items with the same priority. Dijkstra's algorithm doesn't have a restriction that all costs must be unique. You'll need to pick a different data structure as your priority queue. I typically use a std::vector and the heap functions (std::make_heap, std::push_heap, and std::pop_heap) to implement a priority queue for Dijkstra's algorithm.

Share this post


Link to post
Share on other sites

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?

Edited by jcabeleira

Share this post


Link to post
Share on other sites

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?

Yes, it will be duplicated in the priority queue. This does not cause an issue (because the lower cost one will be popped off the queue before the higher cost one, and when the higher cost one is popped off you can just check if the node is already closed and skip processing if it is). Just make sure that you aren't storing pointers in your queue (because then when you update a node, it will also update the node already in the queue, invalidating the queue's sorting).

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. Edited by Cornstalks

Share this post


Link to post
Share on other sites


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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this