
Boost Users : 
Subject: Re: [Boostusers] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?
From: Tristram Gräbener (tristramg_at_[hidden])
Date: 20081022 16:14:56
> I think that your WeightMap should return the result of your CostFunction,
> not the function itself. I'm not familiar with the graph library, though,
> so I don't know if that's easy to do.
The result of the cost function depends on the distance
I believe this is meant to be done with the parameter named
distance_combine (the documentation states that the distance_map and
weight_map do not need to be of the same type).
And it works in my case.
I have :
struct Combine_distance{
float operator()(float distance, FunctionPtr f) const{
return (*f)(distance);
}
};
The weight map value type is FunctionPtr, and I call dijkstra with :
boost::dijkstra_shortest_paths(cg, start_idx,
boost::predecessor_map(&p[0])
.distance_map(&d[0])
.weight_map(get(&Edge_property::length, cg))
.distance_combine(Combine_distance())
);
But of course I have to comment out the check.
> Dijkstra's algorithm only works correctly with nonnegative edge weights, so
> some sort of check is necessary.
Not exactly. If the arcs have constant weights, then yes. If you have
dynamic weights, it's not that simple.
>> 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
>
> This should be sufficient in general, and again, some sort of check is
> necessary.
Of course a check is needed, but should be more flexible with the
condition I gave on the first mail. It should
rather happen when en edge is relaxed
By default distance_compare is < and distance combine is +
So my condition would be :
d[u] < d[u] + w[e]
that is equivalent to w[e] > 0, so edge weight has to be positive.
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net