[boost] [graph] dijkstra_shortest_paths solution stability

Subject: [boost] [graph] dijkstra_shortest_paths solution stability
From: Jan Hudec (bulb_at_[hidden])
Date: 2012-10-17 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]>