Search code examples
javagraph-algorithmbellman-ford

Sedgewick/Wayne "BellmanFordSP.java": how does "findNegativeCycle" make sure a negative cycle is returned?

In the Sedgewick and Wayne implementation of the Bellman-Ford algorithm (https://algs4.cs.princeton.edu/44sp/BellmanFordSP.java) the method findNegativeCycle uses EdgeWeightedDirectedCycle (https://algs4.cs.princeton.edu/44sp/EdgeWeightedDirectedCycle.java) to find a directed cycle in the shortest path tree (the edges in the edgeTo array).

Also, in the check method, it is asserted that the weight of this directed cycle is negative. Thus, if Java assertions are enabled, the BellmanFordSP constructor will throw an exception if the negativeCycle method returns a cycle whose weight is not negative.

Question: if the shortest path tree contains both a zero-weight cycle and a negative-weight cycle, what makes sure that EdgeWeightedDirectedCycle doesn't return the zero-weight cycle (thus causing an assertion failure)?

Solution

  • UPDATE: This bug has been fixed by Kevin Wayne after I emailed him about the issue, by making the weight check in relax include the EPSILON constant (link to code).

    The linked Bellman-Ford implementation does not guarantee that the negative-weight cycle is returned in the presence of both a negative-weight and zero-weight cycle.

    The below graph will cause BellmanFordSP.java to crash (with an AssertionError) when the start vertex is 2, because the weight of the found cycle equals zero (command java -ea BellmanFordSP.java <graph.txt> 2):

    8
9
0 1 3.0
1 2 -3.430337482745286
2 3 0
3 4 -2
4 5 -5
5 0 0
3 6 -4
6 7 -5
7 3 9

    Here's the above graph visualized: graph visualization

    The error is ultimately caused by a floating-point rounding error.

    When vertex 3 is relaxed for the second time, the current distance to this vertex equals -7.430337482745286. The edge 3→6 (of weight -4.0) will cause the distance to 6 to be updated to -7.430337482745286 + -4.0, which (when using double-precision floating-point numbers) equals -11.430337482745287 (note the ending digit is 7 and not 6). When 6 is relaxed, the distance to 7 is updated to -16.430337482745287 (-11.430337482745287 + -5.0) which, finally, causes the relaxation of vertex 7 to update the distance to 3 to -7.430337482745287 (-16.430337482745287 + 9.0). This new distance to 3 is less than the previous distance of -7.430337482745286 (due to the floating-point rounding error), which means the 7→3 edge replaces the 2→3 edge in the shortest path tree. This results in the shortest path tree no longer containing the negative cycle (because it no longer contains 2→3), but the zero-weight cycle instead.