Aaron Windsor wrote:
On 2/12/07, Alejandro Marcos Aragón <aaragon2@uiuc.edu> wrote:
Hi everyone,
I posted this message but I haven't received any response so I decided to post it again. I am trying to store all the vertices with their respective distances from a source within the Dijkstra shortest path algorithm. For that I plan to use a std::vector<std::queue > >. I was able to have the visitor working but I don't know how to access to those values that are computed automatically by the algorithm (d_v, d_u, for example). The code I wrote is as follows:
Hi Alejandro,
I'm not sure I understand your question - The distances from the source vertex are stored in the DistanceMap, and the shortest paths to the source vertex are stored in the PredecessorMap (I'm using the terminology from http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html.) What do you want to store in a vector of queues, i.e. what would the ith queue represent?
Regards, Aaron
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, a^2