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

From: Alejandro Marcos Aragón (aaragon2_at_[hidden])
Date: 2007-03-05 14:14:15

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.

This is what I'm trying to do:
I want to store all the distances for a vertex i, 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. 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.

Alejandro