
Boost : 
Subject: [boost] [graph] dijkstra_shortest_paths solution stability
From: Jan Hudec (bulb_at_[hidden])
Date: 20121017 04:02:26
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_at_[hidden]>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk