AlgorithmsEng

《算法(英文版·第4版)》第678页的 Trace of the Bellman-Ford algorithm (negative cycle) 图的主要部分:

1

这幅图有错误,应改为:

2

这幅图是 Bellman-Ford 算法在含负权重环的加权有向图中寻找最短路径时的运行轨迹。但是书中原来的图有错误,修改如下:

  • 第4幅图应该删除,因为 Bellman-Ford 算法在这之前就因为发现负权重环而结束了。
  • 第3幅图需要修改如下:
    • 边 2→7 需要从黑色改为灰色。
    • edgeTo[4] 的值需要从 0 改为 5,即图中的 4 0->4 0.07 改为 4 5->4 0.07 。
    • edgeTo[7] 的值需要从 2 改为 4,即图中的 7 2->7 0.44 改为 2 4->7 0.44 。