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

Subject: Re: [Boost-users] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?
From: Tristram Gräbener (tristramg_at_[hidden])
Date: 2008-10-22 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 non-negative 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.