Hello, I'm not very familiar yet with all boost::graph internals, but there is something that bothers me: I use a special weight_map (cost functions of my own), providing my own distance_combine. So WeightMap::value_type is CostFunction and DistanceMap::value_type is float 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). However, it uses the distance_compare parameters where "argument types that match the value type of the DistanceMap property map" So it tries to compare my cost function against a float (which of course is not possible). Of course this test garanties the optimality of the algorithm, but it restricts the use to have the weight_map and the distance_map of the same type. Did I miss how to use custom weight_maps, or is it some special case that wasn't thought of ? For now I just commented out the check Thank you ! 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