priority_queue use in dijksta_shortest_paths implementation #7
Description
priority_queue unstable compare function
Inside dijkstra_shortest_paths, the priority_queue is supposed to keep the vertices in order of their distance.
auto qcompare = [&distances](id_type a, id_type b) {
return distances[static_cast<size_t>(a)] > distances[static_cast<size_t>(b)];
};
using Queue = std::priority_queue<id_type, std::vector<id_type>, decltype(qcompare)>;
Queue queue(qcompare);
The ‘distances’ container mutates during the loop (relaxing distances).
The priority_queue is using a compare function that reads the mutating distances container.
This changes the comparison relation between elements already inside the queue, and is not allowed.
And can result in elements getting popped in wrong order.
There’s no way to tell standard heaps and priority_queue that the compare function has changed for a specific element already inside the heap, and reorganize only that one element.
So using standard priority queue, each vertex may have multiple elements in the queue (every time it got relaxed).
I think you can use for the queue element, a struct that will also contain the distance of the node at the time it is pushed (which is after each time it gets relaxed). And the compare function will use the distance saved in the element.
multiple examine per vertex
Once problem one is solved and we can assume that elements get popped out of the queue in correct order, I want to mention another related issue.
The following comment appears at the bottom of the pop loop (from priority queue).
// Note: while we *think* we're done with this vertex, we may not be. If the graph is unbalanced
// and another path to this vertex has a lower accumulated weight, we'll process it again.
// A consequence is that examine_vertex could be called twice (or more) on the same vertex.
I think it is a bit misleading.
It says "another path to this vertex has a lower" as if another time this vertex is popped from the priority queue it could be popped with another distance.
It could say something like "...as the vertex might have been pushed several times to the priority queue from several paths it can be popped more than once..."
Apart from that, there’s also a case for optimizing skipping all but the first time a vertex gets popped, and thus also solving the multiple calls to visitor.examine_vertex.
Because dijkstra doesn't support negative weights, the vertices actually get popped from the priority queue in non-descending order of the final minimal distance they have.
More precisely - the first time a vertex is popped, its distance has already been relaxed as low as it is ever going to be.
Thus all the times that a certain vertex is popped from the priority queue the value in the distance container is already the minimal - it won’t be relaxed further.
When an element is popped, there can also be a way to check whether this vertex has already been examined before, and if it were, can skip it and continue to popping the next element.
So, if for example you choose the solution of keeping the distance at time of pushing into the queue with the element, when it’s popped you can know it’s first time this vertex is examined iff the distance container is equal to what was kept in the queue element.
Requiring that the condition in relax_target is strict comparison (rather than weak), which it is.