java - 塞奇威克/韦恩 "BellmanFordSP.java": how does "findNegativeCycle" make sure a negative cycle is returned?

Question

在 Bellman-Ford 算法 ( https://algs4.cs.princeton.edu/44sp/BellmanFordSP.java ) 的 Sedgewick 和 Wayne 实现中，方法 findNegativeCycle用途 EdgeWeightedDirectedCycle ( https://algs4.cs.princeton.edu/44sp/EdgeWeightedDirectedCycle.java ) 在最短路径树(edgeTo 数组中的边)中找到有向环。
此外，在 check方法，断言这个有向循环的权重是负的。因此，如果启用了 Java 断言，BellmanFordSP如果 negativeCycle 构造函数将抛出异常方法返回一个权重不为负的循环。
问题:如果最短路径树同时包含一个零权重循环和一个负权重循环，那么如何确保 EdgeWeightedDirectedCycle不返回零权重循环(从而导致断言失败)？

Answer 1

链接的 Bellman-Ford 实现不保证在存在负权重和零权重循环的情况下返回负权重循环。
下图将导致 BellmanFordSP.java当起始顶点为 时崩溃(带有 AssertionError ) 2 ，因为找到的循环的权重为零(命令 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

这是上面可视化的图表:
该错误最终是由浮点舍入错误引起的。
当顶点 3 第二次放松，当前到该顶点的距离等于 -7.430337482745286 .边 3→6(权重 -4.0)将导致到 的距离6 更新为 -7.430337482745286 + -4.0 ，其中(当使用
double 浮点数)等于 -11.430337482745287 (注意结尾数字是 7 而不是 6)。
当 6 正在放松，距离 7 更新为 -16.430337482745287 ( -11.430337482745287 + -5.0 ) 最后导致顶点松弛 7 将距离更新为 3 至 -7.430337482745287 ( -16.430337482745287 + 9.0 )。到 的新距离3 小于 -7.430337482745286 的前一个距离(由于浮点舍入误差)，这意味着 7→3 边替换了最短路径树中的 2→3 边。这导致最短路径树不再包含负循环(因为它不再包含 2→3)，而是零权重循环。