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

From: Alejandro Marcos Aragón (aaragon2_at_[hidden])
Date: 2007-03-08 19:38:04

Jens Müller wrote:
> 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.

Thanks for replying. Well, I found out that the easiest way to do what I
wanted to do was to implement my own version of Dijkstra!!! It took me
some time and I still used the library for vertex and edge descriptors.
It works fine and not only I saved the minimum distances but also the
others and I stored them in a min heap (each vertex with a min heap).
My overall experience is that the library was too difficult for me to
use for this and this breaks the purpose of a library, right? I mean, a
library should be written so that users can easily change or modify
something. Well, it was crazy to try to modify the Dijkstra algorithm!
I understand that Dijkstra is implemented in a nice way, using generic
programming and all that stuff, but it is not user friendly at all.
Moreover, what is the purpose of a visitor for an event if you won't be
able to get information from that event? or is it just me that I
couldn't find a way to do this? I tried to find in the documentation an
implementation of a Dijkstra visitor and I didn't find anything at all!
I've been using the library for some time now and this was my first
negative experience.

a^2