https://svn.boost.org/trac10/ticket/13210 <p> Buiding and running the following program with <a class="missing wiki">UndefinedBehaviorSanitizer</a> will generate a report on signed integer overflow error: </p> <pre class="wiki">#include &lt;boost/graph/adjacency_list.hpp&gt; #include &lt;boost/graph/read_dimacs.hpp&gt; #include &lt;boost/graph/successive_shortest_path_nonnegative_weights.hpp&gt; #include &lt;iostream&gt; using namespace boost; using Traits = adjacency_list_traits&lt;vecS, vecS, directedS&gt;; using Graph = adjacency_list&lt; vecS, vecS, directedS, no_property, property&lt;edge_capacity_t, int, property&lt;edge_residual_capacity_t, int, property&lt;edge_reverse_t, Traits::edge_descriptor, property&lt;edge_weight_t, int&gt;&gt;&gt;&gt;&gt;; template &lt;typename Map, typename Edge&gt; void fill_capacity(Map &amp;m, Edge e, Edge er, int c) { put(m, e, c); put(m, er, 0); } template &lt;typename Map, typename Edge&gt; void fill_rev(Map &amp;m, Edge e, Edge er) { put(m, e, er); put(m, er, e); } template &lt;typename Map, typename Edge&gt; void fill_weight(Map &amp;m, Edge e, Edge er, int w) { put(m, e, w); put(m, er, -w); } int main() { Graph g(4); auto capacity = get(edge_capacity, g); auto rev = get(edge_reverse, g); auto weight = get(edge_weight, g); auto e0 = add_edge(0, 1, g).first; auto e0r = add_edge(1, 0, g).first; auto e1 = add_edge(0, 2, g).first; auto e1r = add_edge(2, 0, g).first; auto e2 = add_edge(1, 2, g).first; auto e2r = add_edge(2, 1, g).first; // What the weights and capacities are don't really matter as long as they are all positive fill_capacity(capacity, e0, e0r, 1); fill_capacity(capacity, e1, e1r, 1); fill_capacity(capacity, e2, e2r, 1); fill_rev(rev, e0, e0r); fill_rev(rev, e1, e1r); fill_rev(rev, e2, e2r); fill_weight(weight, e0, e0r, 1); fill_weight(weight, e1, e1r, 1); fill_weight(weight, e2, e2r, 1); successive_shortest_path_nonnegative_weights(g, 0, 2); } </pre><p> Here's the stacktrace collected by UBSan (simplified for readability): </p> <pre class="wiki">/usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:104:57: runtime error: signed integer overflow: 2147483647 + 2147483647 cannot be represented in type 'int' #0 0x43fccd in void boost::successive_shortest_path_nonnegative_weights&lt;...&gt;(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:104:57 #1 0x43d7dc in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch3&lt;...&gt;(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:148:5 #2 0x43bf40 in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch2&lt;...&gt;(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:186:5 #3 0x43b2ba in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch1&lt;...&gt;(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:223:5 #4 0x43b018 in void boost::successive_shortest_path_nonnegative_weights&lt;boost::adjacency_list&lt;...&gt;, int, boost::buffer_param_t, boost::no_property&gt;(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:238:12 #5 0x42b046 in void boost::successive_shortest_path_nonnegative_weights&lt;...&gt;(boost::adjacency_list&lt;...&gt;&amp;, boost::graph_traits&lt;...&gt;::vertex_descriptor, boost::graph_traits&lt;...&gt;::vertex_descriptor) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:255:5 #6 0x42a520 in main /home/grieve/Research/Testing/boost/reduced.cpp:56:3 #7 0x7f7cb22e3f69 in __libc_start_main (/usr/lib/libc.so.6+0x20f69) #8 0x4039b9 in _start (/home/grieve/Research/Testing/boost/reduced+0x4039b9) </pre><p> The problem here is that function successive_shortest_path_nonnegative_weights() does not take into account the fact that its input graph might be disconnected and therefore it is possible for some shortest path distances to be infinity. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/13210 Trac 1.4.3