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