algorithm - 如果我们可以在运行 Bellman Ford 算法后再松弛一次边缘，为什么会存在负循环

Question

我们知道 Bellman Ford 是一种寻找负循环的算法。这是 Bellman Ford 的算法输入:给定图 G(V,E)，w(e) 是权重输出:如果存在负循环，则返回 Yes。

1: set d(s) = 0 and d(v) = 1 for all v (- s
2: for i = 1 ... n-1 do
3:      for every edge (u, v) in G do
4:        if d(v) > d(u) + w(u,v) then
5:           d(v) = d(u) + w(u,v)
6:      end for
7: end for
8: for every edge (u, v) in G do
9:     if d(v) > d(u) + w(u, v) then
10:       return True
11:return False

第 8 行 - 第 11 行是再放宽检测负循环，但如果图中有负循环，为什么这些行保证检测到负循环？

Answer 1

您正在检测这样一个事实，即某对顶点之间的最短路径太长以至于它必须多次访问某个顶点，因此它包含一个循环。如果该循环的长度 >= 0，则删除它最多只能使路径的长度保持不变，因此不会发现它是一种改进。因此，如果您找到这样一条包含循环的最短路径，则该循环的长度必须为负。此外，如果存在一个负长度的循环，它将被发现为从其中的任何顶点返回到同一顶点的最短路径。