设V是图中的顶点集。我知道给定一个图表 |V|没有负循环的顶点，最短路径将始终具有 |V|-1 边。我仍然不太明白为什么要检查每个边缘 |V|-1 次保证了贝尔曼福特的算法将产生最短的路径。有人可以帮助我更好地理解这一点吗？
在第一阶段(检查每条边一次)，您考虑所有可能只有一条边的最短路径。因此，如果最短路径只有一条边，您将在第一阶段之后找到它。(但你还不知道你已经找到了最短的路径。
在检查所有边的第二阶段之后，您将考虑两条边的所有潜在路径，因为您考虑了已考虑的路径的一个边的所有可能的扩展。因此，如果最短路径最多有两个边，您将在第二阶段之后找到它。
等等...如果最短路径最多有 |V|−1 条边(确实如此)，您将在 |V|−1 相。
这是在放松步骤中完成的。在此步骤中，折点距离将逐步更新。直观地说，这些更新在整个图形中传播：当您找到到一个节点的较短路径时，其邻居也可能从此快捷方式中受益。在下一次迭代中，它们也会更新，依此类推。
但这种更新不能无限期地继续下去。它可以发生的最大次数正是|V|- 1.您可以将其可视化为从一个顶点传播到所有其他顶点的更新路径，并传播回源。当然，源本身找不到自己的捷径。
在我看来，有必要做一些数学来完全理解它(尽管其他答案已经给出了一些直觉)。让我们通过归纳来证明以下陈述：
设 s 为源顶点，而您是有向图中的任何其他顶点。在贝尔曼-福特算法迭代之后：
- 如果 d[u] 不是无穷大，则它等于从 S 到你的某条路径的长度。 如果从 S 到你的路径最多
- 有 i 边，那么 d[u] 最多是从 S 到你的最短路径的长度，最多有 i 边。
证明
基本情况为 i=0(在任何迭代之前)。此时，d[s] = 0 且 d[u] = ∞ 对于所有 u。很明显，(1)和(2)对这种情况有效。
让我们考虑它对i(归纳假设)有效。
在 i+1 迭代中，考虑顶点 v 距离更新的时刻 d[v] ：= d[u] + w[u][v]。根据归纳假设，d[u] 是从 s 到你的某条路径的长度。然后 d[u] + w[u][v] 是从源到 v 的路径长度，它遵循从源到你的路径，然后转到 v。因此，(1) 对 (i+1) 次迭代有效，归纳对所有自然 i 有效。
现在，考虑从 s 到 v 的最短路径 P(可能有多个)，最多有 i+1 条边。设 u 是此路径上 v 之前的最后一个顶点。然后，从 s 到你的路径部分是从 s 到你的最短路径，最多有 i 边。事实上，假设它不是。那么就会存在一些从s到u的严格较短的路径，最多有i条边，可以附加到边uv上，得到一条最多i边的路径，严格短于P，这是矛盾的。根据归纳假设，i迭代后的d[u]最多是从s到你的最短路径的长度。因此，d[u] + w[u][v] 最多是 P 的长度。在第 (i+1) 次迭代中，d[v] 与 d[u] + w[u][v] 进行比较，如果 d[u] + w[u][v] 较小，则设置为等于它。因此，在 i+1 迭代后，d[v] 最多是 P 的长度，这是从 s 到 v 的最短路径，最多使用 i+1 条边。因此，(2) 对 (i+1)-th 迭代有效，归纳对所有自然 i 有效。
要完成，请注意，如果有向图有 |V|顶点和无负周期，从源 s 到顶点 u 的最短路径最多有 |V|- 1 边缘。因此，根据之前的结果，贝尔曼-福特确实找到了来自 s 的所有最短路径。
请注意，贝尔曼-福特算法基于递归关系，该关系指出：
d(i,v)是从源到每个节点的最短距离，v它们之间最多有i条边。
随着i增长到i+1，您允许再增加一条边，并且只有在路径长度改进时才更新路径长度。
由于我们知道最短路径最多可以有n-1边，因此没有必要进一步增长i，即最短路径必须是：
d(n-1,v).