貝爾曼-福特演算法

演算法簡介

貝爾曼-福特演算法與迪科斯徹演算法類似，都以鬆弛操作為基礎，即估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。在兩個演算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。

然而，迪科斯徹演算法以貪心法選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而貝爾曼-福特演算法簡單地對所有邊進行鬆弛操作，共|V |? 1次，其中 |V |是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特演算法比迪科斯徹演算法適用於更多種類的輸入。

貝爾曼-福特演算法的最多運行O（|V|·|E|)次，|V|和|E|分別是節點和邊的數量）

matlab代碼實現

*核心代碼

function [minD,path] = BellmanFord(w,start,terminal)% input:% w:圖的帶權鄰接矩陣% start:原點標號% terminal:目的點標號% % output:% minD:起點到終點的最短距離% path:是一個向量，儲存了重源點到目的點的路徑。如果沒有輸入目的點% 則第i位儲存源點到節點i的最短路徑上i的前驅節點%得到必要的參數G = sparse(w);[u,v,c] = find(G);V = size(w,1);E = length(u);f = zeros(1,V);%演算法初始化dist = inf(1,V);dist(start) = 0;%主循環（演算法核心）for k = 1V - 1) for e = 1:E i = u(e);j = v(e); if dist(j) > dist(i) + c(e) dist(j) = dist(i) + c(e); f(j) = i; end endend%負環檢測for e = 1:E i = u(e);j = v(e); if dist(j) > dist(i) + c(e) minD = []; path = 0; return; endend%輸出if nargin == 2 minD = dist; path = f;else minD = dist(terminal); if minD ~= inf %重f中回退 path(1) = terminal; forward = 1; while path(forward) ~= start path(forward + 1) = f(path(forward)); forward = forward + 1; end %調整順序 L = length(path); path = path(L:-1:1); else path = 0;%表示不可達 endendend

*main

w = [0 -1 4 inf inf inf 0 3 2 2 inf inf 0 inf inf inf 1 5 0 inf inf inf inf -3 0];[minD,path] = BellmanFord(w,1)[minD,path] = BellmanFord(w,1,4)

推薦閱讀：