Re: [Boost-users] [BGL] Dijkstra visitor for examine edge event

From: Alejandro Marcos Aragón (aaragon2_at_[hidden])
Date: 2007-02-13 11:29:43

Aaron Windsor wrote:
> On 2/12/07, Alejandro Marcos Aragón <aaragon2_at_[hidden]> 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