
Boost : 
Subject: Re: [boost] shortest path between vertex A and B
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20100224 00:07:48
On Tue, 23 Feb 2010, Alexandre de Morais Amory wrote:
> Hi,
>
> I am starting to use BGL. I manage to read/write in dot format, add few
> attribs, etc.
>
> my next task is to get the set of vertex in the shortest path between vertex
> A and B.
> In a graph like this:
>
> a  b
> b  c
> c  d
>
> assuming 'a' and 'c', the result would be {a,b,c}.
>
> I know it sounds silly, but most similar examples I could find are much
> more complex than this.
> I guess breadth_first_search would solve the problem, but I am having
> trouble with the visitor concept...
> how to implement a visitor to get the set of vertex in the path between two
> points.
>
> Other features of the problem:
> I am assuming an undirected graph. all edges have unitary distances.
> If there are multiple shortest paths between A and B, any of the valid
> solutions can be returned.
You do not need to write your own visitor: the builtin
predecessor_recorder will fill in the path for you. Define a predecessor
property for your graph (either internal to the graph or external), and
then pass boost::record_predecessors(pred_map, boost::on_tree_edge()) as
the visitor to BFS. To get the path, assume that you are searching
for a path from s to t. Run BFS with s as the start vertex. You can get
the path with code like:
std::vector<vertex> path(1, t);
vertex v = t;
while (v != s) {
v = get(pred_map, v);
path.push_back(v);
}
std::reverse(path.begin(), path.end());
If you do not know that there is a path from s to t, initialize the
predecessor map with boost::graph_traits<your_graph>::null_vertex().
After BFS, if get(pred_map, t) is equal to null_vertex(), there is no path
from s to t.
 Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk