On 2/13/07, Alejandro Marcos Aragón
What I want to do is to store all the distances for a vertex i, not only the smallest distance. When an edge is relaxed, meaning that the distance from the source is less than the one before, the distance is overwritten in the DistanceMap. I would like to keep all the distances with their respective vertices. Therefore, I thought that a priority queue (min heap) would be the right data structure to use. However, I don't know how to access to this information using the visitor. Something like this: 3 B------C | / | / 2| /6 | / | / A
Imagine that the A is the source and it finds first that the distance to C is 6 (A-C edge). Then, when it finds that a lower distance is obtained through A-B and B-C (5), I would like to keep the previous result as well in a priority queue. For vertex C the priority queue looks then like this:
(5,B) / / / (6,A)
Of course this example seems trivial but you get the idea. I also tried to understand how the algorithm works in the dijkstra_shortest_paths.hpp but I couldn't find the actual algorithm (the one for which the pseudo-code is given in http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html ). I hope you can help me. Thanks for replying,
Hi Alejandro, Sorry for the delay in the reply. I understand what you're asking now. First, the dijkstra visitor is passed by value, so your visitor will need to contain, say, a shared pointer to a vector instead of a vector. Although it isn't guaranteed by the documentation, the actual implementation of this algorithm in the BGL updates the same DistanceMap property map you pass in to the algorithm before calling edge_relaxed, so you could have the distance to the source available if you also store the DistanceMap in your visitor. So, what you want to do is technically possible, but I would be a little hesitant to use the fact that the actual DistanceMap is updated in the algorithm (and not some temporary.) since that's undocumented. Regards, Aaron