Re: [Boost-users] [BGL] Dijkstra algorithm help!!!

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-03-05 18:13:49

Alejandro Marcos Aragón schrieb:
> Hi, I would like to know if anyone knows about a simplified version of
> the Dijkstra algorithm code. The one in the library is too difficult for
> me to understand and modify since my knowledge about templates is
> limited. I need to modify it somehow to make it do something I want and
> I don't think I can use the visitor concept to do this. I posted a
> message before, where I explained that I was trying to use a visitor to
> solve my problem but I didn't get anywhere.

I remember, although I thought you got answers. Haven't got the thread 
here, though.

> This is what I'm trying to do:
> I want to store all the distances for a vertex i,

"All" meaning all the Dijkstra algorithm ever encountered for that 
vertex, not all meaning for all possible paths, I suppose ...

> not only
> the smallest distance. In the current algorithm, 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.

That would be a min heap for every vertex, i.e. a property map 
(internal, bundled, external, whatever you like) having 
vertex_descriptors as keys and min heaps as values. No problem so far.

> However, I
> don't know how to access to this information using the visitor.
> Imagine a graph like this one:
>                     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)
> 
> I would appreciate any suggestions.

The visitor needs to know how to access the property map, i.e. how to 
get the min heap for a given vertex.