Trac ticket #1009 describes a bad, longstanding bug in the Graph library's handling of overflow in shortest-paths algorithms: http://svn.boost.org/trac/boost/ticket/1009 I would like the attached patch (also attached to the ticket) to be considered for 1.34.1. The problem manifests itself as a bug in the Bellman-Ford algorithm (and probably others), making them produce incorrect results, such as the one reported here: http://lists.boost.org/boost-users/2007/05/28205.php The fix is simple, relatively low-risk, fully tested on Linux with GCC 4.1.1, and solves a rather embarrassing problem in the BGL. - Doug