Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk