詳解貝爾曼福特演算法並以Python實現

貝爾曼福特演算法(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)

以上是詳解貝爾曼福特演算法並以Python實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！