From: Jeffrey Holle (jeffreyholle_at_[hidden])
Date: 2005-12-20 18:48:13
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.pdf
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_at_[hidden] 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_at_[hidden]
> http://listarchives.boost.org/mailman/listinfo.cgi/boost-users