如果没有负权重循环，则 there exists 是从源 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 边的最短路径 .
1 回答
这个陈述是逐字的错误：在所有边都没有权重的图中，没有负权重周期，但每条路径都是最短的 . 我们可以证明的是以下略有（但重要的）不同版本：
如果没有负权重循环，则 there exists 是从源
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边的最短路径 .