如何用Python寫貝爾曼-福德演算法？

如何用Python寫貝爾曼-福特演算法？

貝爾曼-福特演算法（Bellman-Ford Algorithm）是一種解決帶有負權邊的單源最短路徑問題的演算法。本文將介紹如何使用Python編寫貝爾曼-福特演算法，並提供具體程式碼範例。

貝爾曼-福特演算法的核心思想是透過逐步迭代來優化路徑，直到找到最短路徑為止。演算法的步驟如下：

1. 建立一個陣列dist[]，儲存從源點到其他頂點的最短距離。
2. 將dist[]陣列的所有元素初始化為無窮大，但來源點的距離為0。
3. 經過n-1次迭代，對於每條邊(u, v)：
   1) 如果dist[v] > dist[u] weight(u, v)，則更新dist[ v]為dist[u] weight(u, v)。
4. 檢查是否有負權環。對於每條邊(u, v)：
   1) 如果dist[v] > dist[u] weight(u, v)，則存在負權環，無法確定最短路徑。
5. 如果不存在負權環，則最短路徑已經被計算出來，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寫貝爾曼-福德演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！