• Create Account

# Dijsktra and STL Priority Queues

5 replies to this topic

### #1jcabeleira  Members   -  Reputation: 572

Like
0Likes
Like

Posted 18 October 2013 - 08:56 AM

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.

Edited by jcabeleira, 18 October 2013 - 08:57 AM.

### #2powell0  Members   -  Reputation: 596

Like
3Likes
Like

Posted 18 October 2013 - 09:14 AM

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.

### #3Cornstalks  Crossbones+   -  Reputation: 6812

Like
5Likes
Like

Posted 18 October 2013 - 09:24 AM

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.

This (though it could be simpler).

Do not use a std::set for Dijkstra's. It's the wrong data structure. Also, do not use a normal queue or list. The whole difference between breadth-first search (BFS) and Dijkstra's is Dijkstra's uses a priority queue while normal BFS uses a normal queue. That's the only difference (and the only difference between Dijkstra's and A* is an added heuristic).

Use a std::priority_queue.

Edited by Cornstalks, 18 October 2013 - 09:27 AM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #4jcabeleira  Members   -  Reputation: 572

Like
0Likes
Like

Posted 18 October 2013 - 10:16 AM

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, 18 October 2013 - 10:19 AM.

### #5Cornstalks  Crossbones+   -  Reputation: 6812

Like
1Likes
Like

Posted 18 October 2013 - 10:34 AM

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, 18 October 2013 - 10:36 AM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #6jcabeleira  Members   -  Reputation: 572

Like
0Likes
Like

Posted 28 October 2013 - 03:38 AM

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.

PARTNERS