在sedgewick和wayne中实现了bellman-ford算法(https://algs4.cs.princeton.edu/44sp/bellmanfordsp.java)方法 findNegativeCycle 使用 EdgeWeightedDirectedCycle (https://algs4.cs.princeton.edu/44sp/edgeweighteddirectedcycle.java)在最短路径树中寻找一个有向循环 edgeTo 数组）。
另外，在 check 方法，Assert此有向循环的权重为负。因此，如果启用了javaAssert，则 BellmanFordSP 如果 negativeCycle 方法返回权重不为负的循环。
问：如果最短路径树同时包含一个零权循环和一个负权循环，那么什么能确保 EdgeWeightedDirectedCycle 不返回零权重循环（从而导致Assert失败）？
1条答案
按热度按时间gj3fmq9x1#
链接的bellman-ford实现不能保证在存在负权重和零权重循环的情况下返回负权重循环。
下图将导致
BellmanFordSP.java撞车AssertionError)当起始顶点为2时，因为找到的循环的权重等于零（命令java -ea BellmanFordSP.java <graph.txt> 2):上图显示如下：
该错误最终是由浮点舍入错误引起的。
第二次松弛顶点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到5-7.430337482745287(-16.430337482745287 + 9.0). 新距离为3小于以前的距离-7.430337482745286（由于浮点舍入错误），这意味着→3边替换2边→3最短路径树的边。这将导致最短路径树不再包含负循环（因为它不再包含2）→3） ，而是零重量循环。