algorithm - 为什么在 Bellman Ford 算法中需要 (node number - 1) 次迭代来找到最短路径？

Question

图像:4 次迭代，其中 (a) 是原始图。 (b)、(c)、(d)、(e) 对应于每次迭代后的结果。来自“算法介绍 3rd”的例子

你好，我不了解该算法的几个方面。我希望有人能帮忙。以下是我的问题。

在我看来，在每次迭代中，所有的边缘都是松弛的。我希望所有节点都在第一次迭代中更新距离。那么为什么在第一次迭代(b)中，只有节点 t 和 y 的距离被更新而另一个仍然是无穷大？

另一个问题是，为什么需要 (node number - 1) 次所有边都松弛的迭代？保证在每次迭代中实现什么，以便算法必须在 (node number - 1) 时间内运行，以确保只要不存在负权重循环就可以找到最短路径？

Answer 1

只有d[y]的原因和 d[t]在第一次迭代中更新的是这两个顶点是唯一估计与 s 的距离的顶点可以改进。更准确地说，为了 d[v]要在特定迭代中更新，必须有一条边 (u,v)这样 d[u]+w(u,v)<d[v] .也就是说，我们必须能够改进我们对距离 s 的估计。至 v为了更新d[v] .在第一次迭代中，d[u]=inf 的值对于每个顶点 u (s 除外)。因此，如果 v不是 s 的邻居, 然后 u不是 s ，因此 d[u]+w(u,v) 的值等于 inf+w(u,v)=inf .这意味着我们无法改进对 d[v] 的估计。 .这就是为什么只有 s 的邻居即使算法遍历图形的所有边缘，也会在第一次迭代中更新。

至于为什么我们需要n-1迭代，以下两个保证在i之后实现迭代次数:

1. 如果d[u]不是 inf , 那么存在一条长度为 d[u] 的路径来自 s至 u .
2. 如果有一条来自s的路径至 u最多i边，然后 d[u]至多是从 s 开始的最短路径的长度至 u最多i边缘。

从s开始的最短路径的边数至 u不能超过 n-1 (假设没有负循环)。因此，这两个保证(可以通过对 i 的归纳来证明)意味着在 n-1 之后迭代，如果从 s 有一条特定长度的简单路径至 u , 算法找到它。