algorithm - 为什么贝尔曼福特算法中的 |V|-1 次迭代可以保证最短路径？

Question

设 V 为图中的顶点集。我明白，给定一个 |V| 的图表没有负环的顶点，最短路径将始终有 |V|-1 条边。我仍然不太明白为什么检查每条边 |V|-1 次可以保证贝尔曼·福特的算法产生最短路径。有人可以帮助我更好地理解这一点吗？

Answer 1

在第一阶段(检查每条边一次)，您考虑只有一条边的所有潜在最短路径。因此，如果最短路径只有一条边，那么您将在第一阶段之后找到它。 (但是您还不知道您已经找到了最短路径。)

在检查所有边的第二阶段之后，您将考虑两条边的所有潜在路径，因为您考虑了已考虑的路径的一条边的所有可能扩展。因此，如果最短路径最多有两条边，那么您将在第二阶段之后找到它。

依此类推...如果最短路径最多有 |V|−1 条边(确实如此)，那么您将在 |V|− 之后找到它1 阶段。