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).
Maybe I should explain what I'm doing ;) I work on multimodal transportation (combining diffrent means of transport): the time you spend for taking the bus depends on the time you arrive at the bus stop (waiting time) the time you spend on a road edge depends on the time of the day (rush hour or not) And of course the time depends on the path you took before. Thus you can't precalculate the weight (and every edge has a different cost function). A possible work arround would be a operator()<(float) { return true;} to my cost functions.
(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.... The last sentence describing weight_map says that they should be the same type. However, I think that condition could (and should) be relaxed.
Urg, sorry! Indeed it's quite clear... I thought about (on the same page): "The CombineFunction type must be a model of Binary Function. The first argument type of the binary function must match the value type of the DistanceMap property map and the second argument type must match the value type of the WeightMap property map" so I assumed they can be different.
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.
The following patch could do it (but it changes a more general function relax, so I'm not sure of the implications on other algorithms) diff /usr/include/boost/graph/dijkstra_shortest_paths.hpp /usr/include/boost/graph_old/dijkstra_shortest_paths.hpp 120a121,122
if (m_compare(get(m_weight, e), m_zero)) throw negative_edge();
diff /usr/include/boost/graph/relax.hpp /usr/include/boost/graph_old/relax.hpp
16d15
< #include