貝爾曼福特算法(Bellman Ford)可以找到從目標節點到加權圖其他節點的最短路徑。這一點和Dijkstra算法很相似，貝爾曼福特算法可以處理負權重的圖，從實現來看也相對簡單。
貝爾曼福特算法原理詳解
貝爾曼福特算法通過高估從起始頂點到所有其他頂點的路徑長度，迭代尋找比高估路徑更短的新路徑。
因為我們要記錄每個節點的路徑距離，可以將其存儲在大小為n的數組中，n也代表了節點的數量。
實例圖
1、選擇起始節點，并無限指定給其他所有頂點，記錄路徑值。
2、訪問每條邊，并進行松弛操作，不斷更新最短路徑。
3、我們需要這樣做N-1次，因為在最壞的情況下，最短節點路徑長度可能需要重新調整N-1次。
4、注意右上角的節點是如何調整其路徑長度的。
5、在所有節點都有路徑長度之后，再檢查是否存在負環路。
Python實現貝爾曼福特算法
class Graph:
def __init__(self, vertices):
self.V = vertices # Total number of vertices in the graph
self.graph = [] # Array of edges
def add_edge(self, s, d, w):
self.graph.append([s, d, w])
def print_solution(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))
def bellman_ford(self, src):
dist = [float("Inf")] * self.V
dist[src] = 0
for _ in range(self.V - 1):
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
dist[d] = dist[s] + w
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
print("Graph contains negative weight cycle")
return
self.print_solution(dist)
g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)
g.bellman_ford(0)
登錄后復制
