[Boost-users] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?

Subject: [Boost-users] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?
From: Tristram Gräbener (tristramg_at_[hidden])
Date: 2008-10-22 06:23:45

Hello,

I'm not very familiar yet with all boost::graph internals, but there
is something that bothers me:

I use a special weight_map (cost functions of my own), providing my
own distance_combine.
So WeightMap::value_type is CostFunction and DistanceMap::value_type is float

The dijkstra algorithm checks if an edge has a positive weight (
boost/graph/dijkstra_shortest_paths.hpp lines 121 & 122 with version
1.36.0).
However, it uses the distance_compare parameters where "argument types
that match the value type of the DistanceMap property map"
So it tries to compare my cost function against a float (which of
course is not possible).

Of course this test garanties the optimality of the algorithm, but it
restricts the use to have the weight_map and the distance_map of the
same type.

Did I miss how to use custom  weight_maps, or is it some special case
that wasn't thought of ? For now I just commented out the check

Thank you !

PS: a more general optimality condition is (sufficient, but I'm not
sure if it's necessary) : the combine function has to be non
decreasing :
for a node u, and edge e = (u,v), the distance_map d and the weight map w
distance_compare(d[u], distance_combine(d[u], w[e]) ) has to be true