为什么我们需要最多放松所有边缘（V-1）

为了理解这个例子，建议对 Bellman-Ford 单源最短路径算法有一个简要的想法，可以在这里找到

在 Bellman-Ford 算法中，为了找出最短路径，我们需要放松图形的所有边缘。该过程最多重复 （V-1） 次，其中 V 是图中顶点的数量。

找出从源到所有其他顶点的最短路径所需的迭代次数取决于我们选择放宽边缘的顺序。

我们来看一个例子：

这里，源顶点是 1.我们将找出源和所有其他顶点之间的最短距离。我们可以清楚地看到，为了到达顶点 4 ，在最坏的情况下，它将采用 （V-1） 边缘。现在，根据发现边的顺序，发现顶点 4 可能需要 （V-1） 次。没得到吗？让我们用 Bellman-Ford 算法找出最短的路径： ****

我们将使用这个序列：

+--------+--------+--------+--------+
| `Serial` |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

对于我们的第一次迭代：

1. d [3] + 成本[3] [4] = 无穷大。它不会改变任何东西。
2. d [2] + 成本[2] [3] = 无穷大。它不会改变任何东西。
3. d [1] + 成本[1] [2] = 2 < d [2] 。 d [2] = 2 。父[2] = 1 。

我们可以看到我们的放松过程只改变了 d [2] 。我们的图表看起来像：

第二次迭代：

1. d [3] + 成本[3] [4] = 无穷大。它不会改变任何东西。
2. d [2] + 成本[2] [3] = 5 < d [3] 。 d [3] = 5 。父[3] = 2。
3. 它不会改变。

这次放松过程改变了 d [3] 。我们的图表看起来像：

第三次迭代：

1. d [3] + 成本[3] [4] = 7 < d [4] 。 d [4] = 7 。父[4] = 3 。
2. 它不会改变。
3. 它不会改变。

我们的第三次迭代终于找到了从 1 到 4 的最短路径。我们的图表看起来像： ****

因此，需要 3 次迭代才能找到最短路径。在这之后，无论我们放松边缘多少次， d []中的值都将保持不变。现在，如果我们考虑另一个序列：

+--------+--------+--------+--------+
| `Serial` |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

我们得到：

1. d [1] + 成本[1] [2] = 2 < d [2] 。 d [2] = 2 。
2. d [2] + 成本[2] [3] = 5 < d [3] 。 d [3] = 5 。
3. d [3] + 成本[3] [4] = 7 < d [4] 。 d [4] = 5 。

我们的第一次迭代找到了从源到所有其他节点的最短路径。另一序列 1-> 2 ， 3-> 4 ， 2-> 3 是可能的，这会给我们后的最短路径 2 次迭代。我们可以做出这样的决定：无论我们如何安排序列，在这个例子中，从源头找出最短路径不会超过 3 次迭代。 ****

我们可以得出结论，对于最好的情况，它需要 1 次迭代才能找到来自源的最短路径。对于最坏的情况，它将进行 （V-1） 次迭代，这就是为什么我们重复放松 （V-1） 次的过程。