[graph] dijkstra_shortest_paths solution stability
Hello All, I need to implement an algorithm, that uses dijkstra's algorithm as key component. However it has two additional requirements on it: 1. If for any two vertices u, v there is an edge and a path of the same length through additional vertices, the direct edge is always selected and 2. If for any two vertices u, v there is more than one shortest path, all calculates shortest path trees that include path u, v contain the same path between those vertices. Now the article that describes the algorithm uses additional property with random values to disambiguate the paths, but I am sure the following two simple rules will achieve the effect more easily: 1. When u is reached at the same distance through two vertices, v and w, the one with lower distance from start will be used in the shortest path tree. 2. When u is reached at the same distance through two vertices, v and w, that both have the same distance from start, the one that comes first in some arbitrary fixed total ordering will be used inthe shortest path tree. These rules are trivially implementable by: 1. Not updating the parent map if the new distance is not strictly less. 2. Using additional criterion in the heap comparing the vertices by index or descriptor if they have the same tentative distance. Now I suspect rule 1 is already satisfied though it's not documented. And if rule 2 is not satisfied, would it be more generally useful and worth, possibly optionally, implementing in the library? -- Jan 'Bulb' Hudec <bulb@ucw.cz>
On Oct 17 2012, Jan Hudec wrote:
Hello All,
I need to implement an algorithm, that uses dijkstra's algorithm as key component. However it has two additional requirements on it:
1. If for any two vertices u, v there is an edge and a path of the same length through additional vertices, the direct edge is always selected and 2. If for any two vertices u, v there is more than one shortest path, all calculates shortest path trees that include path u, v contain the same path between those vertices.
Now the article that describes the algorithm uses additional property with random values to disambiguate the paths, but I am sure the following two simple rules will achieve the effect more easily:
1. When u is reached at the same distance through two vertices, v and w, the one with lower distance from start will be used in the shortest path tree. 2. When u is reached at the same distance through two vertices, v and w, that both have the same distance from start, the one that comes first in some arbitrary fixed total ordering will be used inthe shortest path tree.
These rules are trivially implementable by:
1. Not updating the parent map if the new distance is not strictly less. 2. Using additional criterion in the heap comparing the vertices by index or descriptor if they have the same tentative distance.
Now I suspect rule 1 is already satisfied though it's not documented. And if rule 2 is not satisfied, would it be more generally useful and worth, possibly optionally, implementing in the library?
Would it work to use std::pair<double, int> as distance_type combining distance and the index of the predecessor vertex, and having associated combine and compare functions? // a = vertex_distance // b = edge_weight distance_type combine(const distance_type& a, const distance_type& b) { return std::make_pair(closed_plus(a.first,b.first), b.second); } bool compare(const distance_type& a, const distance_type& b) { return a.first < b.first || (a.first == b.first && a.second < b.second); }
On Wed, Oct 17, 2012 at 9:12 AM, Alex Hagen-Zanker <ahh34@cam.ac.uk> wrote:
On Oct 17 2012, Jan Hudec wrote:
Hello All,
I need to implement an algorithm, that uses dijkstra's algorithm as key component. However it has two additional requirements on it:
1. If for any two vertices u, v there is an edge and a path of the same length through additional vertices, the direct edge is always selected and 2. If for any two vertices u, v there is more than one shortest path, all calculates shortest path trees that include path u, v contain the same path between those vertices.
Now the article that describes the algorithm uses additional property with random values to disambiguate the paths, but I am sure the following two simple rules will achieve the effect more easily:
1. When u is reached at the same distance through two vertices, v and w, the one with lower distance from start will be used in the shortest path tree. 2. When u is reached at the same distance through two vertices, v and w, that both have the same distance from start, the one that comes first in some arbitrary fixed total ordering will be used inthe shortest path tree.
These rules are trivially implementable by:
1. Not updating the parent map if the new distance is not strictly less. 2. Using additional criterion in the heap comparing the vertices by index or descriptor if they have the same tentative distance.
Now I suspect rule 1 is already satisfied though it's not documented. And if rule 2 is not satisfied, would it be more generally useful and worth, possibly optionally, implementing in the library?
Would it work to use std::pair<double, int> as distance_type combining distance and the index of the predecessor vertex, and having associated combine and compare functions?
Yup. I've done exactly that in the past (slightly different problem, but same solution). THK
// a = vertex_distance // b = edge_weight distance_type combine(const distance_type& a, const distance_type& b) { return std::make_pair(closed_plus(a.first,b.first), b.second); }
bool compare(const distance_type& a, const distance_type& b) { return a.first < b.first || (a.first == b.first && a.second < b.second);
}
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Timothy H. Keitt http://www.keittlab.org/
participants (3)
-
Alex Hagen-Zanker -
Jan Hudec -
Tim Keitt