Though I'd pipe in a way to find a path between two vertices within a tree. This is a required step in implementing a network simplex method algorithm, which I've done. Its based on Vasik Chvatal's Linear Programming book. He has a chunk of this book on-line that describes most of the path finding algorithm: http://www.esc.auckland.ac.nz/teaching/Engsci450FC/NetworksModule/NOChapter4... The algorithm employs depth and predecessor arrays. These need to be initialized from your tree. The above mentioned pdf tells how. I found that boost.graph is set up quite well to initialize them. If your task is finding the path between a lot of vertices on a static tree, it could be efficiently used. This is mainly because the paths from the target and from the source can be found "at the same time". matthieu.ferrant@agfa.com wrote:
Hi Dmitry, Gregoire, zvrba, Aaron, Vladimir,
thanks for your answers to my question.
Gregoire, Vladimir, I initially tried using an all-pairs shortest path algorithm but with a graph of 30.000 nodes or more, the distance matrix is just way to large. That's why I was doing multiple Dijkstras.
Reading the other remarks, I actually ended up doing 2 dijkstras: the first one from an arbitrary end-point, then looping over the distance vector, selecting the end point with the largest distance value associated to it. This is point is then used for a second dijkstra, where I also loop over all end points to determine the other end-point. Finally using the predecessor visitor, and both end points, it is easy to record the full path. This I believe this somewhat boils down to what Aaron wrote. Dmitry, I didn't try out your implementation, looks like it might be a little faster, but what's the overhead of dijkstra vs BFS ? Probably not that much in a tree.
Thanks alot for all the help so far !!
matt-
------------------------------------------------------------------------
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users