向我解释 Bellman Ford 算法的方式是它经过 n-1(n 是节点数)次迭代，在每次迭代中更新节点之间的距离。所有图形示例都显示了初始化为无穷大的节点，并且最接近源节点的节点在第一次迭代中被更新，但其余节点保持在无穷大，直到发生到达它们的迭代为止。
但是，查看算法的代码，例如提供的代码 here ，我发现很难理解为什么所有距离比迭代次数多的节点没有用算法更新。例如，如果我正在进行第二次迭代并且我有一个只能通过路径 a-b-c-d 访问的节点 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 被正确更新？例如，如果算法按 a-b-c-d 的顺序遍历节点，我不明白为什么算法不存储节点 b 的距离信息，移动到节点 c，为其存储距离信息，最后到达 d足够的信息来计算第一次迭代中的最短路径。
我希望这能说得通。
最佳答案
它可能发生 - 但它不是保证。您只能保证在第 k 次迭代时(而不是更早的时候)拥有长度不超过 k 的最短路径。
您看到的可视化只是为了解释算法的概念，使用事务内存模型更清晰、更容易理解。
想一想，如果距离为 10 的节点在第一次迭代中发生变化，那么使用可视化来理解算法是多么困难...
关于评论中的问题:
Does that mean I could effectively create a tool that tracks the number of changes per iteration, and once that counter reaches 0, I could exit the iterations early?
是的，如果迭代 k 没有变化 - 迭代 k+1 也不能改变任何东西，一切都是最小的，对于 k+2 , ...
关于python - 很难理解 Bellman Ford 的迭代，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14363655/