检测图中的负循环

要理解这个例子，建议你对 Bellman-Ford 算法有一个简要的了解，可以在这里找到

使用 Bellman-Ford 算法，我们可以检测图中是否存在负循环。我们知道，为了找出最短路径，我们需要放宽图形的所有边缘 （V-1） 次，其中 V 是图中顶点的数量。我们已经看到，在这个例子中 ，在 （V-1） 次迭代之后，无论我们做了多少次迭代，我们都无法更新 d [] 。或者我们可以吗？

如果图中存在负循环，即使在 （V-1） 次迭代之后，我们也可以更新 d [] 。发生这种情况是因为在每次迭代中，遍历负循环总是会降低最短路径的成本。这就是 Bellman-Ford 算法将迭代次数限制为 （V-1）的原因。如果我们在这里使用 Dijkstra 算法 ，我们将陷入无限循环。但是，让我们集中精力寻找负面循环。

我们假设，我们有一个图表：

让我们选择顶点 1 作为源。在将 Bellman-Ford 的单源最短路径算法应用于图形之后，我们将找出从源到所有其他顶点的距离。

这是图 （V-1） = 3 次迭代后的图形。它应该是结果，因为有 4 个边，我们最多需要 3 次迭代才能找到最短的路径。因此，这是答案，或者图表中存在负的权重周期。为了找到这一点，在 （V-1） 次迭代之后，我们再进行一次最后的迭代，如果距离继续减小，则意味着图中肯定存在负的权重周期。

对于这个例子：如果我们检查 2-3 ， d [2] + cost [2] [3] 将给出 1 小于 d [3] 。因此，我们可以得出结论，我们的图表中存在负循环。

那么我们如何找出负循环呢？我们对 Bellman-Ford 程序做了一些修改：

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

这就是我们如何确定图表中是否存在负循环。我们还可以修改 Bellman-Ford 算法以跟踪负循环。