[BGL] saving all-pair shortest paths
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? Thanks, Shyam
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
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
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
On Mon, 12 Oct 2009, Shyamendra Solanki wrote:
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.
I would think it would pick the first edge with the same weight as the edge on the optimal path; does it do something else? As to why there is no predecessor matrix, I do not know; the code is very old and I did not write it. I do not think it would be too hard to add if you wanted to (to either algorithm). -- Jeremiah Willcock
I would think it would pick the first edge with the same weight as the edge
on the optimal path; does it do something else?
well, it can pick any edge if that is the shortest path to its endpoint
vertex. this edge need not be in shortest paths to all vertex.
I think I'll use a patched version as you suggested. Thanks Jeremiah.
-Shyam
On Mon, Oct 12, 2009 at 8:34 PM, Jeremiah Willcock
On Mon, 12 Oct 2009, Shyamendra Solanki wrote:
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.
I would think it would pick the first edge with the same weight as the edge on the optimal path; does it do something else? As to why there is no predecessor matrix, I do not know; the code is very old and I did not write it. I do not think it would be too hard to add if you wanted to (to either algorithm).
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Tue, 13 Oct 2009, Shyamendra Solanki wrote:
I would think it would pick the first edge with the same weight as the edge on the optimal path; does it do something else?
well, it can pick any edge if that is the shortest path to its endpoint vertex. this edge need not be in shortest paths to all vertex.
What do you mean? I think the algorithm I suggested would give a shortest path tree from each source vertex. Is there something I'm misunderstanding?
I think I'll use a patched version as you suggested. Thanks Jeremiah.
OK. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock -
Shyamendra Solanki