Re: [boost] [graph] dijkstra_shortest_paths solution stability

Subject: Re: [boost] [graph] dijkstra_shortest_paths solution stability
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2012-10-18 16:59:57

On Wed, Oct 17, 2012 at 9:12 AM, Alex Hagen-Zanker <ahh34_at_[hidden]> 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/