Boost logo

Boost :

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);
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, gregod at, cpdaniel at, john at