Re: [boost] shortest path between vertex A and B

Subject: Re: [boost] shortest path between vertex A and B
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-02-24 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 built-in 
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