Re: [Boost-users] [BGL] saving all-pair shortest paths

Subject: Re: [Boost-users] [BGL] saving all-pair shortest paths
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-10-09 10:38:25

On Fri, 9 Oct 2009, Shyamendra Solanki wrote:

> Hi,
>
>   I understand that both the floyd-warshall and johnson algorithms  populate the DistanceMatrix for shortest distances between any
> pair of vertices.
>   Could you give some hint how to get the actual shortest paths?

It appears that there is no direct way to get this information, so you 
will need to reconstruct it from the distance matrix.  Roundoff errors 
might end up breaking this calculation, but it will probably work.  If you 
want to find the path from s to t, do something like:

std::vector<vertex> path(1, s);
vertex v = s;
do {
   bool found = false;
   for e in out_edges(v, g) {
     if (distancematrix[s][target(e)] ==
           distancematrix[s][v] + weight[e]) {
       v = target(e);
       found = true;
       break;
     }
   }
   assert (found);
   path.push_back(v);
} while (v != t);

Having a predecessor matrix directly in the algorithm would be better, 
though, since that would give exactly the same paths the algorithm found 
during its run.

-- Jeremiah Willcock