Re: [boost] [graph] dijkstra_shortest_paths solution stability

Subject: Re: [boost] [graph] dijkstra_shortest_paths solution stability
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-10-17 10:12:21

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);
}