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