Bellman-Ford算法部分证明
Proof of part of Bellman-Ford Algorithm
如何在 Bellman-Ford 算法中证明这一点：
如果没有负权重循环，则从源s到汇t的每条最短路径最多有n-1条边，其中n是图中的顶点数。
有什么想法吗？
该声明逐字是错误的：在所有边都具有零权重的图中，没有负权重循环，但每条路径都是最短的。
我们可以证明的是以下稍微（但重要）不同的版本：
如果没有负权重循环，则存在一条从源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 条边的最短路径存在。
如何在 Bellman-Ford 算法中证明这一点：
如果没有负权重循环，则从源s到汇t的每条最短路径最多有n-1条边，其中n是图中的顶点数。
有什么想法吗？
该声明逐字是错误的：在所有边都具有零权重的图中，没有负权重循环，但每条路径都是最短的。 我们可以证明的是以下稍微（但重要）不同的版本：
如果没有负权重循环，则存在一条从源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 条边的最短路径存在。