[Boost-bugs] [Boost C++ Libraries] #12701: Numerical error cause invalid input to dijkstra algorithm in min cost max flow code

Subject: [Boost-bugs] [Boost C++ Libraries] #12701: Numerical error cause invalid input to dijkstra algorithm in min cost max flow code
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-12-19 16:50:55

#12701: Numerical error cause invalid input to dijkstra algorithm in min cost max
flow code
--------------------------------------------+------------------------------
 Reporter:  Dmitrii Marin <dmitry.marin@…>  |       Type:  Bugs
   Status:  new                             |  Milestone:  To Be Determined
Component:  None                            |    Version:  Boost 1.61.0
 Severity:  Problem                         |   Keywords:
--------------------------------------------+------------------------------
 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.

 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));

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/12701>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.