如何用Python編寫貝爾曼-福特算法？
貝爾曼-福特算法（Bellman-Ford Algorithm）是一種解決帶有負權邊的單源最短路徑問題的算法。本文將介紹如何使用Python編寫貝爾曼-福特算法，并提供具體代碼示例。
貝爾曼-福特算法的核心思想是通過逐步迭代來優化路徑，直到找到最短路徑為止。算法的步驟如下：
- 創建一個數組dist[]，存儲從源點到其他頂點的最短距離。將dist[]數組的所有元素初始化為無窮大，但源點的距離為0。通過n-1次迭代，對于每條邊(u, v)：
1) 如果dist[v] > dist[u] + weight(u, v)，則更新dist[v]為dist[u] + weight(u, v)。檢查是否存在負權環。對于每條邊(u, v)：
1) 如果dist[v] > dist[u] + weight(u, v)，則存在負權環，無法確定最短路徑。如果不存在負權環，則最短路徑已經被計算出來，dist[]數組即為最短路徑。
以下是用Python編寫的貝爾曼-福特算法的代碼示例：
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def bellman_ford(self, src):
dist = [float("Inf")] * self.V
dist[src] = 0
for _ in range(self.V - 1):
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print("圖中存在負權環，無法確定最短路徑")
return
self.print_solution(dist)
def print_solution(self, dist):
print("頂點 最短距離")
for i in range(self.V):
print(i, " ", dist[i])
# 示例用法
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)
登錄后復制
以上示例中，創建了一個圖g，并添加了一些邊。接著調用bellman_ford方法來計算最短路徑并打印結果。在這個示例中，源點是0，最短路徑將被計算出來。
貝爾曼-福特算法的時間復雜度為O(V*E)，其中V是頂點數，E是邊數。在實際應用中，如果圖中存在負權環，算法將不會停止，而會進入無限循環。因此，在使用貝爾曼-福特算法時，應先檢查是否存在負權環。
以上就是如何用Python編寫貝爾曼-福德算法？的詳細內容，更多請關注www.xfxf.net其它相關文章！
