Sedgewick/Wayne“BellmanFordSP.java”：“findNegativeCycle”如何确保返回负循环？

Question

在 Bellman-Ford 算法的 Sedgewick 和 Wayne 实现中 (https://algs4.cs.princeton.edu/44sp/BellmanFordSP.java)，方法

findNegativeCycle

使用

EdgeWeightedDirectedCycle

(https://algs4) .cs.princeton.edu/44sp/EdgeWeightedDirectedCycle.java）在最短路径树中查找有向循环（

edgeTo

数组中的边）。

此外，在

check

方法中，断言该有向循环的权重为负。因此，如果启用了 Java 断言，如果

BellmanFordSP

方法返回权重不为负的循环，则

negativeCycle

构造函数将抛出异常。

问题：如果最短路径树包含两个一个零权重环和一个负权重环，那么如何确保

EdgeWeightedDirectedCycle

不会返回零权重环（从而导致断言失败）？

Answer 1

更新： 在我向 Kevin Wayne 发送有关该问题的电子邮件后，此错误已由 Kevin Wayne 修复，方法是在

relax

中进行权重检查，包括 EPSILON 常量（代码链接）。

链接的 Bellman-Ford 实现不能保证在存在负权重和零权重循环的情况下返回负权重循环。

当起始顶点为

2

时，下图将导致

BellmanFordSP.java

崩溃（带有 AssertionError），因为找到的循环权重为零（命令

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

，这（当使用 双精度浮点数）等于

-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），而是零权循环。