[Graph] how to find all shortest paths (not just one of them)?
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) cheers, Erik Sjölund
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)
I coded up something like this a couple of years ago. My approach was to keep running a shortest paths algorithm until I ran out of paths. The tricky part is that you have to invalidate each shortest path as you go. I did this by using a color map for edges. White means a viable edge, black means you've already used it and can't re-cross it. This approach isn't actually correct and you can prove that it won't find all shortest paths with a fairly simple counterexample. It might be made correct if you associate a path with each vector (or edge?) and disallow traversals based on more that information rather than a simple white/black coloring. The naive approach might be a good place to start. Andrew
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
participants (3)
-
Andrew Sutton -
Erik Sjölund -
Jeremiah Willcock