I'm using dijkstra_shortest_paths with a custom compare function like (Weight a, Weight b) { return a<=b; } As I've also got some zero weight edges within the graph this leads to problems with the test for negative weights in dijkstra_bfs_visitor's examine_edge-function. The test fails on checking zero weight edges and throws a negative_edge-exception (dijkstra_shortest_paths.hpp:190): if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero)) evaluates to if(0<=0) Any suggestions on how to solve this issue? For now I just got rid of the test, as I just use unsigned weight values, but of course that's not a sound solution.