[BGL] Dijkstra algorithm help!!!
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
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.
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
participants (2)
-
Alejandro Marcos Aragón -
Jens Müller