Re: [Boost-users] [Graph] how to find all shortest paths (not just one of them)?

Subject: Re: [Boost-users] [Graph] how to find all shortest paths (not just one of them)?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-11-03 10:11:37

On Wed, 3 Nov 2010, Erik Sjölund wrote:

> Hi,
> I managed to record a shortest path between two vertices by doing
>
> adjacency_list < vecS, vecS, undirectedS > g;
> std::vector<Vertex> p(boost::num_vertices(g));
> Vertex vertex = *(boost::vertices(g).first);
> boost::breadth_first_search(g, vertex,
>  boost::visitor(
>    boost::make_bfs_visitor(
>      boost::record_predecessors(&p[0],  boost::on_tree_edge())
>    )
>  )
> );
>
> The shortest path can be found by inspecting the vector p. But my goal
> is slightly different.
>
> Does anyone know how to "record" all shortest paths between two
> vertices? (i.e. all paths having the minimal path length)

Are you looking for all paths that have the same length as the shortest 
path?  If so, brandes_betweenness_centrality() does that computation. 
See the IncomingMap there, which is a generalization of the predecessor 
map to allow multiple predecessors.

-- Jeremiah Willcock