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_searchWikipedia'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