DSA Bellman-Ford 演算法
Bellman-Ford 演算法
Bellman-Ford 演算法最適合用於查詢有向圖中，從源頂點到所有其他頂點的最短路徑，該圖有一個或多個負邊權重。
它透過重複檢查圖中所有邊是否存在更短的路徑來實現這一點，檢查的次數等於圖中的頂點數（減 1）。
Bellman-Ford 演算法也可用於具有正邊（有向和無向）的圖，就像 Dijkstra 演算法一樣，但在這種情況下，Dijkstra 演算法是首選，因為它更快。
在具有負環的圖上使用 Bellman-Ford 演算法將無法產生最短路徑結果，因為在負環中，我們可以總能多繞一圈並獲得更短的路徑。
負環是我們可以圍繞它走的路徑，其中邊權重的總和為負。
幸運的是，Bellman-Ford 演算法可以實現為安全地檢測和報告負環的存在。
工作原理
- 將源頂點的初始距離設定為零，將所有其他頂點的初始距離設定為無窮大。
- 對於每條邊，檢查是否可以計算出更短的距離，如果計算出的距離更短，則更新距離。
- 檢查所有邊（步驟 2） \(V-1\) 次。這是圖中頂點數 (\(V\)) 減去一的次數。
- 可選：檢查負環。稍後將更詳細地解釋這一點。
上面 Bellman-Ford 演算法的動畫只顯示了當檢查邊導致距離更新時，而不是所有不導致距離更新的其他邊檢查。
手動演練
Bellman-Ford 演算法實際上相當直接，因為它使用鄰接矩陣檢查所有邊。每次檢查都是為了檢視透過該邊從一邊頂點到達另一邊頂點是否可以獲得更短的距離。
並且這種對所有邊的檢查會進行 \(V - 1\) 次，其中 \(V\) 是圖中的頂點數。
這就是 Bellman-Ford 演算法在我們圖上檢查所有鄰接矩陣中的邊 5-1=4 次的方式
已檢查所有邊 0 次。
我們圖中檢查的前四條邊是 A->C、A->E、B->C 和 C->A。這前四條邊的檢查不會導致最短距離的任何更新，因為這些邊都以無窮大距離的起始頂點開始。
在檢查完來自頂點 A、B 和 C 的邊之後，將檢查來自 D 的邊。由於起點（頂點 D）的距離為 0，因此 A、B 和 C 的更新距離是來自頂點 D 的出邊權重。
接下來檢查的邊是來自頂點 E 的邊，這會導致頂點 B 和 C 的距離更新。
Bellman-Ford 演算法已檢查所有邊 1 次。演算法將額外檢查所有邊 3 次，然後才能完成，因為 Bellman-Ford 將檢查所有邊（圖中頂點數減 1）的次數。
演算法開始第二次檢查所有邊，首先檢查來自頂點 A 的出邊。檢查邊 A->C 和 A->E 不會導致距離更新。
下一個要檢查的邊是從頂點 B 出發的邊 B->C。這會導致從頂點 D 到 C 的距離更新為 5-4=1。
檢查邊 C->A，會導致頂點 A 的距離更新為 1-3=-2。
Bellman-Ford 演算法第二輪中對邊 C->A 的檢查實際上是導致此特定圖的距離更新的最後一次檢查。演算法將繼續檢查另外 2 次所有邊，而不會更新任何距離。
在 Bellman-Ford 演算法中檢查所有邊 \(V-1\) 次可能看起來很多，但它會進行這麼多次以確保始終能找到最短路徑。
Bellman-Ford 演算法的實現
實現 Bellman-Ford 演算法與 我們實現 Dijkstra 演算法的方式非常相似。
我們首先建立 Graph 類，其中 __init__、add_edge 和 add_vertex 方法將用於建立我們要執行 Bellman-Ford 演算法以找到最短路徑的特定圖。
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = databellman_ford 方法也放在 Graph 類中。正是這個方法執行 Bellman-Ford 演算法。
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
return distances第 18-19 行：開始時，除了源頂點本身（距離設定為 0）之外，所有頂點的距離都設定為從源頂點開始的無窮長距離。
第 21 行：所有邊都會被檢查 \(V-1\) 次。
第 22-23 行：雙重 for 迴圈會檢查鄰接矩陣中的所有邊。對於每個頂點 u，檢查指向頂點 v 的邊。
第 24-26 行：如果邊存在，並且計算出的距離比現有距離更短，則更新到該頂點 v 的距離。
完整的程式碼，包括我們特定圖的初始化以及執行 Bellman-Ford 演算法的程式碼，如下所示
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
return distances
g = Graph(5)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_edge(3, 0, 4) # D -> A, weight 4
g.add_edge(3, 2, 7) # D -> C, weight 7
g.add_edge(3, 4, 3) # D -> E, weight 3
g.add_edge(0, 2, 4) # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5) # A -> E, weight 5
g.add_edge(4, 2, 3) # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2) # E -> B, weight 2
# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
distances = g.bellman_ford('D')
for i, d in enumerate(distances):
print(f"Distance from D to {g.vertex_data[i]}: {d}")Bellman-Ford 演算法中的負邊
說 Bellman-Ford 演算法找到“最短路徑”並不直觀，因為我們如何繪製或想象負距離呢？因此，為了更容易理解，我們可以說 Bellman-Ford 找到的是“最便宜的路徑”。
在實踐中，Bellman-Ford 演算法可以幫助我們找到運輸路線，其中邊權重代表燃油成本和其他東西，減去透過這兩個頂點之間的邊所產生的金錢。
考慮到這種解釋，邊 C->A 的 -3 權重可能意味著從 C 到 A 的燃油成本為 5 美元，而我們透過在 C 取件並在 A 交付來獲得 8 美元的報酬。所以我們最終賺取的比花費的多 3 美元。因此，透過我們上面圖中的 D->E->B->C->A 交付路線可以賺取總共 2 美元。
Bellman-Ford 演算法中的負環
如果我們可以在圖中形成環路，並且該環路的邊權重總和為負，那麼我們就存在一個負環。
透過將邊 C->A 的權重從 -3 改為 -9，我們得到了兩個負環：A->C->A 和 A->E->C->A。每次我們使用 Bellman-Ford 演算法檢查這些邊時，我們計算和更新的距離就會越來越低。
負環的問題在於最短路徑不存在，因為我們可以總是多繞一圈來獲得更短的路徑。
因此，在 Bellman-Ford 演算法中實現負環檢測很有用。
Bellman-Ford 演算法中負環的檢測
在執行 Bellman-Ford 演算法，檢查圖 \(V-1\) 次所有邊之後，所有最短路徑都找到了。
但是，如果圖包含負環，並且我們再多檢查一次所有邊，我們會在最後一輪中至少找到一個更短的距離，對嗎？
因此，為了在 Bellman-Ford 演算法中檢測負環，在檢查完 \(V-1\) 次所有邊之後，我們只需要再檢查一次所有邊，如果我們在這最後一次檢查中找到了更短的距離，我們就可以得出結論：一定存在一個負環。
下面是 bellman_ford 方法，包含了負環檢測，執行在我們上面具有負環（由於 C->A 邊的權重為 -9）的圖上
示例
Python
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
# Negative cycle detection
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
return (True, None) # Indicate a negative cycle was found
return (False, distances) # Indicate no negative cycle and return distances第 30-33 行：所有邊會再檢查一次，以檢視是否存在負環。
第 34 行：返回 True 表示存在負環，並且返回 None 而不是最短路徑，因為在具有負環的圖中找到最短路徑沒有意義（因為透過再檢查一次所有邊總能找到更短的路徑）。
第 36 行：返回 False 表示沒有負環，並且可以返回 distances。
從 Bellman-Ford 演算法返回路徑
我們目前正在查詢最短路徑的總權重，例如“從 D 到 A 的距離：-2”是執行 Bellman-Ford 演算法的結果。
但是，透過在放鬆每條邊時記錄每個頂點的 predecessor，我們可以在後續程式碼中使用它來列印結果，包括實際的最短路徑。這意味著我們可以提供更多資訊，除了路徑權重之外還有實際路徑：“D->E->B->C->A，距離：-2”。
這個最後的程式碼示例是 Bellman-Ford 演算法的完整程式碼，包括我們到目前為止討論的所有內容：查詢最短路徑的權重、檢測負環以及查詢實際的最短路徑
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
predecessors[v] = u
print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
# Negative cycle detection
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
return (True, None, None) # Indicate a negative cycle was found
return (False, distances, predecessors) # Indicate no negative cycle and return distances
def get_path(self, predecessors, start_vertex, end_vertex):
path = []
current = self.vertex_data.index(end_vertex)
while current is not None:
path.insert(0, self.vertex_data[current])
current = predecessors[current]
if current == self.vertex_data.index(start_vertex):
path.insert(0, start_vertex)
break
return '->'.join(path)
g = Graph(5)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_edge(3, 0, 4) # D -> A, weight 4
g.add_edge(3, 2, 7) # D -> C, weight 7
g.add_edge(3, 4, 3) # D -> E, weight 3
g.add_edge(0, 2, 4) # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5) # A -> E, weight 5
g.add_edge(4, 2, 3) # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2) # E -> B, weight 2
# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
negative_cycle, distances, predecessors = g.bellman_ford('D')
if not negative_cycle:
for i, d in enumerate(distances):
if d != float('inf'):
path = g.get_path(predecessors, 'D', g.vertex_data[i])
print(f"{path}, Distance: {d}")
else:
print(f"No path from D to {g.vertex_data[i]}, Distance: Infinity")
else:
print("Negative weight cycle detected. Cannot compute shortest paths.")第 19 行：predecessors 陣列儲存了最短路徑中每個頂點的 predecessor 頂點。
第 28 行：每次放鬆邊時，predecessors 陣列都會用新的 predecessor 頂點進行更新。
第 40-49 行：get_path 方法使用 predecessors 陣列為每個頂點生成最短路徑字串。
Bellman-Ford 演算法的時間複雜度
Bellman-Ford 演算法的時間複雜度主要取決於巢狀迴圈。
外層 for 迴圈執行 \(V-1\) 次，或者在有負環檢測的情況下執行 \(V\) 次。對於具有許多頂點的圖，將所有邊檢查的次數減一與頂點數相比差異很小，因此我們可以說外層迴圈對時間複雜度貢獻 \(O(V)\)。
兩個內層 for 迴圈檢查圖中的所有邊。如果我們假設最壞情況的時間複雜度，那麼我們有一個非常稠密的圖，其中每個頂點都有到每個其他頂點的邊，因此對於所有頂點 \(V\)，必須檢查到所有其他頂點 \(V\) 的邊，這會給時間複雜度帶來 \(O(V^2)\) 的貢獻。
所以總的來說，我們得到 Bellman-Ford 演算法的時間複雜度
\[ O(V^3) \]
然而，在實際情況中，特別是對於稀疏圖，這意味著每個頂點只連線到其他頂點的一小部分，兩個內層 for 迴圈檢查所有邊的複雜度可以從 \(O(V^2)\) 近似為 \(O(E)\)，我們得到 Bellman-Ford 的總時間複雜度
\[ O(V \cdot E) \]
Bellman-Ford 演算法的時間複雜度比 Dijkstra 演算法慢，但 Bellman-Ford 可以找到負邊圖中的最短路徑，並且可以檢測負環，而 Dijkstra 演算法無法做到。
