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 23:03:00

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

Well, that's something I didn't consider.  I'm sure you're right.
Now I'm just being curious.  If your cost function is the same for every
edge, you could move the real work of the cost function to the combine
method.  (If it varies between graphs, you could make the function pointer a
member of the struct.)  The weight_map could then return some other value
that the cost function uses (or ignores).

(the documentation states that the distance_map and weight_map do not need
> to be of the same type).

Since I just read it, I feel I should correct that.
http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths.html
The last sentence describing weight_map says that they should be the same
type.  However, I think that condition could (and should) be relaxed.

As for the discussion of the edge-checking condition, every description of
Dijkstra's algorithm that I've read says that it only guarantees a correct
answer when edges have non-negative weights.  Really, we can generalize that
to "compare(d[u], combine(d[u], w[e])) must be true," as you stated.  I
don't know how to do that with this library, since examine_edge considers
the edge, but not the distance.  I suspect that it will require interface
changes, though they may be minor.  Again, I'm not familiar with the
library, only with the algorithm.