單源最短路徑演算法（假設圖中存在負迴圈）

Created: November-22, 2018

在閱讀這個例子之前，需要對邊緣鬆弛有一個簡短的想法。你可以從這裡學到它

Bellman-Ford 演算法計算從單個源頂點到加權有向圖中所有其他頂點的最短路徑。即使它比 Dijkstra 演算法慢，但它適用於邊緣權重為負且在圖中也發現負權重週期的情況。Dijkstra 演算法的問題是，如果存在負迴圈，則會一次又一次地繼續迴圈並繼續減小兩個頂點之間的距離。

該演算法的思想是以一些隨機順序逐個遍歷該圖的所有邊緣。它可以是任何隨機順序。但是你必須確保，如果 uv （其中 u 和 v 是圖中的兩個頂點）是你的一個命令，那麼必須有一個從 u 到 v 的邊。通常它直接取自給定輸入的順序。同樣，任何隨機順序都可以。

選擇順序後，我們將根據放鬆公式放鬆邊緣。對於從 u 到 v 的給定邊緣 uv ，鬆弛公式為： **** ****

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

也就是說，如果從源到任何頂點的距離 u + 邊緣 uv 的權重小於從源到另一個頂點 v 的距離，我們更新從源到 v 的距離。我們需要放鬆邊緣最多 （V-1） 次，其中 V 是圖中邊的數量。為什麼 （V-1） 你問？我們將在另一個例子中解釋它。此外，我們將跟蹤任何頂點的父頂點，也就是當我們放鬆邊緣時，我們將設定：

parent[v] = u

這意味著我們找到了另一條通過 u 到達 v 的較短路徑。稍後我們將需要它來列印從源到目標頂點的最短路徑。 **** ****

我們來看一個例子。我們有一個圖表： StackOverflow 文件

我們選擇 1 作為源頂點。我們想要找出從源到所有其他頂點的最短路徑。

首先， d [1] = 0，因為它是源。休息是無限的，因為我們還不知道他們的距離。

我們將按順序放鬆邊緣：

+--------+--------+--------+--------+--------+--------+--------+
| `Serial` |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

你可以採取任何你想要的順序。如果我們放鬆一下邊緣，我們得到什麼？我們得到從源到最多使用 1 個邊的路徑的所有其他頂點的距離。現在讓我們放鬆邊緣並更新 d [] 的值。我們得到：

d [4] + 成本[4] [5] = 無窮大 + 7 = 無窮大。我們無法更新這個。
d [2] + 成本[3] [4] = 無窮大。我們無法更新這個。
d [1] + 成本[1] [2] = 0 + 2 = 2 < d [2] 。所以 d [2] = 2 。還父[2] = 1 。
d [1] + 成本[1] [4] = 4 。所以 d [4] = 4 < d [4] 。父[4] = 1 。
d [4] + 成本[4] [6] = 9 。 d [6] = 9 < d [6] 。父[6] = 4 。
d [2] + 成本[2] [2] = 無窮大。我們無法更新這個。

我們無法更新某些頂點，因為 d[u] + cost[u][v] ![StackOverflow 文件]( d[v] 條件不匹配。正如我們之前所說，我們使用最大 1 個邊緣找到了從源到其他節點的路徑。 <https://i.stack.imgur.com/Pkhx2.png)

我們的第二次迭代將為我們提供使用 2 個節點的路徑。我們得到：

d [4] + 成本[4] [5] = 12 < d [5] 。 d [5] = 12 。父[5] = 4 。
d [3] + 成本[3] [4] = 1 < d [4] 。 d [4] = 1 。父[4] = 3 。
d [3] 保持不變。
d [4] 保持不變。
d [4] + 成本[4] [6] = 6 < d [6] 。 d [6] = 6 。父[6] = 4 。
d [3] 保持不變。

我們的圖表看起來像： StackOverflow 文件

我們的第 3 次迭代只會更新頂點 5 ，其中 d [5] 將為 8 。我們的圖表看起來像： StackOverflow 文件

在此之後，無論我們進行多少次迭代，我們都將擁有相同的距離。因此，我們將保留一個標誌，檢查是否發生任何更新。如果沒有，我們將簡單地退出迴圈。我們的虛擬碼將是：

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
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]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

為了跟蹤負迴圈，我們可以使用此處描述的過程修改我們的程式碼。我們完成的虛擬碼將是：

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
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]
            parent[v] := u
            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 d

列印路徑：

要列印到頂點的最短路徑，我們將迭代回其父級，直到找到 NULL 然後列印頂點。虛擬碼將是：

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

複雜：

由於我們需要放寬邊緣最大 （V-1） 次，因此如果我們使用 adjacency list 來表示圖，則該演算法的時間複雜度將等於 O（V * E） ，其中 E 表示邊的數量。但是，如果使用 adjacency matrix 來表示圖形，則時間複雜度將為 O（V ^ 3） 。原因是我們可以在使用 adjacency list 時在 O(E) 時間迭代所有邊緣，但是當使用 adjacency matrix 時需要 O（V ^ 2） 時間。