貝爾曼福特算法(Bellman Ford)可以找到從目標(biāo)節(jié)點(diǎn)到加權(quán)圖其他節(jié)點(diǎn)的最短路徑。這一點(diǎn)和Dijkstra算法很相似，貝爾曼福特算法可以處理負(fù)權(quán)重的圖，從實(shí)現(xiàn)來(lái)看也相對(duì)簡(jiǎn)單。
貝爾曼福特算法原理詳解
貝爾曼福特算法通過(guò)高估從起始頂點(diǎn)到所有其他頂點(diǎn)的路徑長(zhǎng)度，迭代尋找比高估路徑更短的新路徑。
因?yàn)槲覀円涗浢總€(gè)節(jié)點(diǎn)的路徑距離，可以將其存儲(chǔ)在大小為n的數(shù)組中，n也代表了節(jié)點(diǎn)的數(shù)量。
實(shí)例圖
1、選擇起始節(jié)點(diǎn)，并無(wú)限指定給其他所有頂點(diǎn)，記錄路徑值。
2、訪(fǎng)問(wèn)每條邊，并進(jìn)行松弛操作，不斷更新最短路徑。
3、我們需要這樣做N-1次，因?yàn)樵谧顗牡那闆r下，最短節(jié)點(diǎn)路徑長(zhǎng)度可能需要重新調(diào)整N-1次。
4、注意右上角的節(jié)點(diǎn)是如何調(diào)整其路徑長(zhǎng)度的。
5、在所有節(jié)點(diǎn)都有路徑長(zhǎng)度之后，再檢查是否存在負(fù)環(huán)路。
Python實(shí)現(xiàn)貝爾曼福特算法
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)
登錄后復(fù)制
