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

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

Cool, I wondered what the application was. Now it makes sense.

I figured that your edges would have different cost functions, but thought I should mention it anyway.

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

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.

That does imply that they can be different...I'd say one or both of those statements needs to change.

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 <boost/graph/exception.hpp>
53,55d51
< if ( compare(combine(d_u, w_e), d_u) ) {
< throw negative_edge();
< }

Well, the Bellman-Ford algorithm includes the same header, and so probably uses the same function. Since it works with negative edges (but not negative cycles), this patch isn't the way to go.

Do you think I should contact the dev mailing list in order to get an opinion more of the internals ?

Since nobody else is weighing in on this discussion, and all my knowledge of the graph library was learned in the last 24 hours, I'd say yes. Be sure to mention the discrepancy in the documentation about value types.

This is just wishful thinking on my part, but I wonder if the distance could be incorporated into the edge descriptor, or the vertex descriptor? I imagine that would require even more changes, but it would allow weight_map to calculate the edge weight, and examine_edge could stay as-is.