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

Subject: Re: [Boost-users] [BGL] saving all-pair shortest paths
From: Shyamendra Solanki (shyamendra_at_[hidden])
Date: 2009-10-12 01:32:22

This doesn't work. It always selects the first outgoing edge's endpoint
vertex, which may not be in path.

Was the predecessor matrix avoided to meet some design goal? i don't
understand.

-Shyam

On Fri, Oct 9, 2009 at 8:08 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>