On Wed, May 18, 2011 at 12:34 PM, Nishchal Devnur wrote: Hi, I am looking for a implementation in boost that is efficient in finding a
path between two vertices in a given tree. I am right now using the
unidrected adjancency list to store the tree. Given a node u and node v I
would like to find the path between these two nodes in the tree. Any
suggestions is greatly appreciated ! If your edges are weighted, then you should look into Dijkstra's Algorithm:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
If your edges all have the same weight, then a standard breadth-first search
is sufficient:
http://en.wikipedia.org/wiki/Breadth-first_search
Wikipedia's article on BFS is a bit misleading in your case since you might
think it says you have to start at the root of your tree. In fact you should
just start from your "u" node and progress outwards -- the u node is the
"root" of a notional tree that is superimposed on your normal graph.
-Chris