How to record all the shortest paths from a source

Question

I'm currently using Boost graph library's dijkstra algorithm http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html to compute shortest distance path between a pair of vertices. So far, I can only obtain one shortest path stored in the predecessor map.

So my question is: is it possible to let the function return all possible shortest paths between a pair of vertices?

Answer 1

No, you need to build that yourself. One way is to compute distances from the source vertex s (in G) and to the sink vertex t (i.e., distances from t in the transpose graph) using two calls to Dijkstra. Then, extract a subgraph containing exactly those nodes u such that distance(s, u) + distance(u, t) = distance(s, t) and those arcs uv such that distance(s, u) + length(u, v) + distance(v, t) = distance(s, t) and recursively enumerate all s-t paths in this subgraph.