我如何在贝尔曼福特算法中证明这一点：
如果没有负权重循环，那么从源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为止。
这仍然是一条最短的路。
证明了存在一个具有CC＞边的最短路径。
关于algorithm - Bellman-Ford算法一部分的证明，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50511158/