3

贝尔曼福特算法向我解释的方式是它经过 n-1 次（n 是节点数）迭代，每次迭代更新节点之间的距离。所有图形示例都显示了初始化为无穷大的节点，最接近源节点的节点在第一次迭代中被更新，但其余的保持在无穷大，直到发生到达它们的迭代。

但是，查看算法的代码，例如此处提供的代码，我发现很难理解为什么所有步数大于迭代次数的节点都没有使用算法进行更新。例如，如果我正在进行第二次迭代，并且我有一个只能通过路径 abcd 访问的节点 d，那么我读过的示例似乎表明 d 直到第 4 次迭代才会更新。

但是代码的主要松弛函数：

def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # Record this lower distance
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

根据给出与前任节点源的权重和距离的信息进行更新。如果算法在每次迭代中迭代每个节点，那么在第一次迭代中如何阻止 d 正确更新？例如，如果算法以 abcd 的顺序迭代节点，我不明白为什么该算法不会存储节点 b 的距离信息，移动到节点 c，存储距离信息，最后到达 d足够的信息来计算第一次迭代中的最短路径。

我希望这有点道理。

4

1 回答 1

4

它可能会发生 - 但不能保证。您只能保证k在第 k 次迭代时拥有最短路径，而不是更早。

您看到的可视化只是为了解释算法的概念，使用事务内存模型更清晰、更容易理解。
想想如果距离为 10 的节点在第一次迭代中会发生变化，那么使用可视化来理解算法有多难......

关于评论中的问题：

这是否意味着我可以有效地创建一个工具来跟踪每次迭代的更改次数，并且一旦该计数器达到 0，我就可以提前退出迭代？

是的，如果迭代没有变化k——迭代也不k+1能改变任何东西，一切都是最小的，for k+2, ...

于 2013-01-16T17:11:03.363 回答