Re: [Boost-users] To find a path between two vertices in a tree.

Subject: Re: [Boost-users] To find a path between two vertices in a tree.
From: Chris Weisiger (cweisiger_at_[hidden])
Date: 2011-05-18 15:50:56

On Wed, May 18, 2011 at 12:34 PM, Nishchal Devnur <nishchal.devnur_at_[hidden]
> 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