Boost C++ Libraries: Ticket #12701: Numerical error cause invalid input to dijkstra algorithm in min cost max flow code https://svn.boost.org/trac10/ticket/12701 <p> Line 46 of successive_shortest_path_nonnegative_weights.hpp computes a new weight for Dijkstra algorithm. The weigh is guaranteed to be non-negative in theory. In practice numerical rounding errors may make it a small negative number causing the failure of Dijkstra algorithm. </p> <p> Do something like this for floating point types: return std::max(value_type(0), get(distance_, source(v, g_)) - get(distance_, target(v, g_)) + get(weight_, v)); </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/12701 Trac 1.4.3 Dmitrii Marin <dmitry.marin@…> Mon, 19 Dec 2016 16:51:36 GMT version changed https://svn.boost.org/trac10/ticket/12701#comment:1 https://svn.boost.org/trac10/ticket/12701#comment:1 <ul> <li><strong>version</strong> <span class="trac-field-old">Boost 1.61.0</span> → <span class="trac-field-new">Boost 1.63.0</span> </li> </ul> Ticket Dmitrii Marin <dmitry.marin@…> Mon, 19 Dec 2016 16:51:55 GMT version changed https://svn.boost.org/trac10/ticket/12701#comment:2 https://svn.boost.org/trac10/ticket/12701#comment:2 <ul> <li><strong>version</strong> <span class="trac-field-old">Boost 1.63.0</span> → <span class="trac-field-new">Boost Development Trunk</span> </li> </ul> Ticket Kohei Takahashi Tue, 20 Dec 2016 00:53:42 GMT component changed; owner set https://svn.boost.org/trac10/ticket/12701#comment:3 https://svn.boost.org/trac10/ticket/12701#comment:3 <ul> <li><strong>owner</strong> set to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>component</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">graph</span> </li> </ul> Ticket