为什么在 Bellman Ford 算法中需要 (node number - 1) 次迭代来找到最短路径？
Why need (node number - 1) iterations in Bellman Ford algorithm to find shortest paths?
图像：4次迭代，其中（a）是原始图。 (b)、(c)、(d)、(e) 对应于每次迭代后的结果。来自 "Introduction to Algorithm 3rd"
的示例
你好，
我不了解该算法的几个方面。我希望有人能帮忙。以下是我的问题。
在我看来，在每次迭代中，所有的边缘都是松弛的。我希望所有节点都在第一次迭代中更新距离。那么为什么在第一次迭代（b）中，只有节点 t 和 y 的距离被更新而另一个仍然是无穷大？
另外一个问题是，为什么需要(node number - 1)次所有边都松弛的迭代？保证在每次迭代中实现什么，以便算法必须 运行 在 (node number - 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次迭代后得到以下两个保证：
- 如果
d[u]不是inf，则存在从s到u的长度d[u]的路径。
- 如果有一条从
s到u的路径最多有i条边，那么d[u]至多是从s 到 u，最多 i 个边。
从s到u的最短路径的边数不能超过n-1（假设没有负循环）。因此，这两个保证（可以通过 i 上的归纳法证明）意味着在 n-1 次迭代之后，如果存在从 s 到 u 的特定长度的简单路径，算法找到它。
纯粹的归纳证明是有说服力的，但很难得到。由于缺少示例，我看到的大多数答案都不容易得到。
在我看来，如果你有一些归纳的基础知识，proof of correctness就足够简单易懂了。同样，理解它是正确的并不意味着你很容易理解为什么 -> 因为最短路径中最多 (N-1) 个节点，我必须循环 (N-1) 次？
归纳之后，我认为最重要的一点是每个循环中的 BF 过程不保证边的特定顺序：您可以按任意顺序处理边，并且循环N-1次仍得出正确答案。.
现在用一个很简单的案例来帮助大家理解：
结论：（附示例中的部分）。另外，在最坏的情况下，当你有一条长度为 (N-1) 的最短路径时，并且每个第 i 个循环你只在最短路径中放宽源节点之后的第 i 个节点，你将需要(N-1) 循环。在我们的示例中，在情况 2 中，对于节点 3，第一个循环仅设法放松节点 2，它是 P(1,3) 上源之后的第一个节点，因此您需要另一个循环来放松。
图像：4次迭代，其中（a）是原始图。 (b)、(c)、(d)、(e) 对应于每次迭代后的结果。来自 "Introduction to Algorithm 3rd"
的示例你好， 我不了解该算法的几个方面。我希望有人能帮忙。以下是我的问题。
在我看来，在每次迭代中，所有的边缘都是松弛的。我希望所有节点都在第一次迭代中更新距离。那么为什么在第一次迭代（b）中，只有节点 t 和 y 的距离被更新而另一个仍然是无穷大？
另外一个问题是，为什么需要(node number - 1)次所有边都松弛的迭代？保证在每次迭代中实现什么，以便算法必须 运行 在 (node number - 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次迭代后得到以下两个保证：
- 如果
d[u]不是inf，则存在从s到u的长度d[u]的路径。 - 如果有一条从
s到u的路径最多有i条边，那么d[u]至多是从s到u，最多i个边。
从s到u的最短路径的边数不能超过n-1（假设没有负循环）。因此，这两个保证（可以通过 i 上的归纳法证明）意味着在 n-1 次迭代之后，如果存在从 s 到 u 的特定长度的简单路径，算法找到它。
纯粹的归纳证明是有说服力的，但很难得到。由于缺少示例，我看到的大多数答案都不容易得到。
在我看来，如果你有一些归纳的基础知识，proof of correctness就足够简单易懂了。同样，理解它是正确的并不意味着你很容易理解为什么 -> 因为最短路径中最多 (N-1) 个节点，我必须循环 (N-1) 次？
归纳之后，我认为最重要的一点是每个循环中的 BF 过程不保证边的特定顺序：您可以按任意顺序处理边，并且循环N-1次仍得出正确答案。.
现在用一个很简单的案例来帮助大家理解：
结论：（附示例中的部分）。另外，在最坏的情况下，当你有一条长度为 (N-1) 的最短路径时，并且每个第 i 个循环你只在最短路径中放宽源节点之后的第 i 个节点，你将需要(N-1) 循环。在我们的示例中，在情况 2 中，对于节点 3，第一个循环仅设法放松节点 2，它是 P(1,3) 上源之后的第一个节点，因此您需要另一个循环来放松。