檢測圖中的負迴圈

要理解這個例子，建議你對 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 演算法以跟蹤負迴圈。