https://svn.boost.org/trac10/ticket/1009 <p> As reported here </p> <blockquote> <p> <a class="ext-link" href="http://lists.boost.org/boost-users/2007/05/28205.php"><span class="icon">​</span>http://lists.boost.org/boost-users/2007/05/28205.php</a> </p> </blockquote> <p> the Bellman-Ford shortest paths algorithm fails to compute correct results in some graphs containing negative cycles. The cause of the problem is the incorrect overflow handling in closed_plus, which is used to relax edges in the graph. The attached patch fixes the problem. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/1009 Trac 1.4.3 Douglas Gregor Tue, 29 May 2007 15:38:14 GMT https://svn.boost.org/trac10/ticket/1009 https://svn.boost.org/trac10/ticket/1009 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">bellman-ford-neg-cycle.patch</span> </li> </ul> <p> Fix handling of overflow </p> Ticket Douglas Gregor Tue, 29 May 2007 16:53:59 GMT https://svn.boost.org/trac10/ticket/1009#comment:1 https://svn.boost.org/trac10/ticket/1009#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> <li><strong>milestone</strong> → <span class="trac-field-new">Boost 1.34.1</span> </li> </ul> Ticket anonymous Thu, 20 Mar 2008 04:49:23 GMT https://svn.boost.org/trac10/ticket/1009#comment:2 https://svn.boost.org/trac10/ticket/1009#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">closed</span> → <span class="trac-field-new">reopened</span> </li> <li><strong>resolution</strong> <span class="trac-field-deleted">fixed</span> </li> </ul> <p> This solution breaks the floyd_warshall_all_pairs_shortest_paths (which uses this as the default <a class="missing wiki">BinaryPredicate</a>) in the case that one of the parameters is infinity and the other parameter is a negative number. </p> Ticket Jeremiah Willcock Tue, 27 Jan 2009 20:06:11 GMT https://svn.boost.org/trac10/ticket/1009#comment:3 https://svn.boost.org/trac10/ticket/1009#comment:3 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Douglas Gregor</span> to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>status</strong> <span class="trac-field-old">reopened</span> → <span class="trac-field-new">new</span> </li> </ul> Ticket Jeremiah Willcock Tue, 27 Jan 2009 20:06:26 GMT https://svn.boost.org/trac10/ticket/1009#comment:4 https://svn.boost.org/trac10/ticket/1009#comment:4 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> Ticket Jeremiah Willcock Tue, 27 Jan 2009 20:06:41 GMT https://svn.boost.org/trac10/ticket/1009#comment:5 https://svn.boost.org/trac10/ticket/1009#comment:5 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> Probably fixed in <a class="changeset" href="https://svn.boost.org/trac10/changeset/50808" title="Changed closed_plus to match inf_plus from floyd_warshall_test, ...">r50808</a> (fix for <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/1164" title="#1164: Bugs: Floyd Warshall broken with unsigned edge weights (closed: fixed)">#1164</a> which is also related to overflow handling). </p> Ticket