On Fri, Oct 9, 2009 at 8:08 PM, Jeremiah Willcock <jewillco@osl.iu.edu> 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@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users