algorithm - Bellman-Ford算法部分证明

Question

如何在 Bellman-Ford 算法中证明这一点:

如果没有负权重循环，则从源 s 到汇 t 的每条最短路径至多有 n-1 边，其中 n 是图中的顶点数。

有什么想法吗？

Answer 1

该陈述逐字逐句是错误的:在所有边的权重为零的图中，没有负权重循环，但每条路径都是最短的。我们可以证明的是以下稍微(但重要)不同的版本:

如果没有负权重循环，则存在到源的最短路径s到水槽 t最多有 n - 1边缘，其中 n是图中的顶点数。

---

这是证明。假设有一条最短路径>= n边缘。那么这个路径有> n顶点。根据鸽巢原理，有两个顶点相同。所以我们可以去掉一部分路径，改造s -> (sequence-1) -> v -> (sequence-2) -> v -> (sequence-3) -> t进入刚刚s -> (sequence-1) -> v -> (sequence-3) -> t .周期长度v -> (sequence-2) -> v是非负的，所以我们的新路径并不比旧路径差。而旧款自称是最短的，再好不过了。总之，这些意味着我们删除了一个零权重的循环。

重要的是，由于我们删除了至少一次出现的 v，因此在我们的过程中顶点数量减少了。 .现在，重复上述过程，直到路径小于n。边缘。它仍然是最短路径。所以，我们用< n证明了最短路径边缘存在。