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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-02-21 21:50:03

On 2/13/07, Alejandro Marcos Aragón <aaragon2_at_[hidden]> wrote:

<snip>

> 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