
Boost Users : 
Subject: Re: [Boostusers] [Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?
From: Dave Steenburgh (dave.steenburgh_at_[hidden])
Date: 20081022 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 nonnegative 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.
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