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: Dave Steenburgh (dave.steenburgh_at_[hidden])
Date: 2008-10-22 15:52:13

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

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 dijkstra algorithm checks if an edge has a positive weight
> (boost/graph/dijkstra_shortest_paths.hpp lines 121 & 122 with
> version 1.36.0).  ....  For now I just commented out the check

Dijkstra's algorithm only works correctly with non-negative edge weights, so
some sort of check is necessary.

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