algorithm - 如果我们在运行贝尔曼福特算法后可以再放松一次边缘，为什么会存在负循环

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，则删除它最多会使路径的长度保持不变，因此不会发现它是一种改进。因此，如果您找到这样一条最短路径，其中包含一个循环，则该循环的长度必须为负。此外，如果有一个负长度的循环，它将被视为从其中的任何顶点返回到同一顶点的最短路径。