Boost logo

Boost :

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).


> // 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:

Timothy H. Keitt

Boost list run by bdawes at, gregod at, cpdaniel at, john at