貝爾曼-福特演算法

貝爾曼-福特演算法
概況
類別	最短路徑問題（針對帶權有向圖）
資料結構	圖
複雜度
平均時間複雜度	{{#statements:P3754}}
最壞時間複雜度	<math>O \left (
最佳時間複雜度	{{#statements:P3753}}
空間複雜度	<math>O (
相關變量的定義

貝爾曼-福特演算法（英語：Bellman–Ford algorithm），求解單源最短路徑問題的一種演算法，由理查德·貝爾曼和小萊斯特·倫道夫·福特創立。有時候這種演算法也被稱為貝爾曼-福特-摩爾演算法（Bellman–Ford–Moore algorithm），因為愛德華·F·摩爾也為這個演算法的發展做出了貢獻。它的原理是對圖進行<math> |V|-1</math>次鬆弛操作，得到所有可能的最短路徑。其優於戴克斯特拉演算法的方面是邊的權值可以為負數、實現簡單，缺點是時間複雜度過高，高達<math>O (|V| |E|)</math>。但演算法可以進行若干種最佳化，提高了效率。

演算法

File:Bellman-Ford worst-case example.svg

-1</math>步或<math>4</math>次計算路徑長度。相反地，若邊以最佳順序處理，從左到右，演算法只需要在一次遍歷內完成。

貝爾曼-福特演算法與戴克斯特拉演算法類似，都以鬆弛操作為基礎，即估計的最短路徑值漸漸地被更加準確的值替代，直至得到最佳解。在兩個演算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。然而，戴克斯特拉演算法以貪婪法選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而貝爾曼-福特演算法簡單地對所有邊進行鬆弛操作，共<math>|V|-1</math>次，其中<math> |V| </math>是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特演算法比戴克斯特拉演算法適用於更多種類的輸入。

貝爾曼-福特演算法的最多執行<math>O(|V|\cdot|E|)</math>（大O符號）次，<math>|V|</math>和<math>|E|</math>分別是節點和邊的數量）。

偽代碼

BellmanFord(G, source):

    for each vertex v in G: \\初始化
        dist[v] = infinity
        parent[v] = null

    dist[source] = 0

    for i = 1 to |V| - 1:   \\遍历
        for each edge (u, v) with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u

    for each edge (u, v) with weight w:
        if dist[u] + w < dist[v]:
            return "存在负权环" \\检查负权环

    return dist, parent

原理

循環

每次循環操作實際上是對相鄰節點的訪問，第<math>n</math>次循環操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過<math>|V|-1</math>條邊，所以可知貝爾曼-福特演算法所得為最短路徑。

負邊權操作

與戴克斯特拉演算法不同的是，戴克斯特拉演算法的基本操作「拓展」是在深度上尋路，而「鬆弛」操作則是在廣度上尋路，這就確定了貝爾曼-福特演算法可以對負邊進行操作而不會影響結果。

負權環判定

因為負權環可以無限制的降低總花費，所以如果發現第<math>n</math>次操作仍可降低花銷，就一定存在負權環。

尋找負迴路

當使用這個演算法尋找最短路徑時，有負迴路會使演算法找不到正確的答案。但是，由於在找到負迴路後會中止演算法，所以可以被用來尋找目標，例如在網絡流分析中的消圈演算法(Cycle Cancellation Algorithms)

最佳化

循環的提前跳出

在實際操作中，貝爾曼-福特演算法經常會在未達到<math>|V| - 1</math>次前就出解，<math>|V| - 1</math>其實是最大值。於是可以在循環中設置判定，在某次循環不再進行鬆弛時，直接退出循環，進行負權環判定。

佇列最佳化

主條目：最短路徑快速演算法

西南交通大學的段凡丁於1994年提出了用佇列來最佳化的演算法。鬆弛操作必定只會發生在最短路徑前導節點鬆弛成功過的節點上，用一個佇列記錄鬆弛過的節點，可以避免了冗餘計算。原文中提出該演算法的複雜度為<math>O(k|E|)</math>，<math>k</math>是個比較小的係數，但該結論被證明不適于于所有情況。

Pascal語言範例

Begin
  initialize-single-source(G,s);
  initialize-queue(Q);
  enqueue(Q,s);
  while not empty(Q) do 
    begin
      u:=dequeue(Q);
      for each v∈adj[u] do 
        begin
          tmp:=d[v];
          relax(u,v);
          if (tmp<>d[v]) and (not v in Q) then
            enqueue(Q,v);
        end;
    end;
End;

C++語言範例

int SPFA(int s) {
	std::queue<int> q;
	bool inq[maxn] = {false};
	for(int i = 1; i <= N; i++) dis[i] = 2147483647;
	dis[s] = 0;
	q.push(s); inq[s] = true;
	while(!q.empty()) {
		int x = q.front(); q.pop();
		inq[x] = false;
		for(int i = front[x]; i !=0 ; i = e[i].next) {
			int k = e[i].v;
			if(dis[k] > dis[x] + e[i].w) {
				dis[k] = dis[x] + e[i].w;
				if(!inq[k]) {
					inq[k] = true;
					q.push(k);
				}
			}
		}
	}
	for(int i =  1; i <= N; i++) std::cout << dis[i] << ' ';
	std::cout << std::endl;
	return 0;
}

樣例

例：

<math>V=\{v_1,v_2,v_3,v_4\}, E=\{(v_1,v_2),(v_1,v_3),(v_2,v_4),(v_4,v_3)\}</math>，<math>weight(v_1,v_2)=-1,weight(v_1,v_3)=3,weight(v_2,v_4)=3,weight(v_4,v_3)=-1</math>。

執行如表： <math>D:\texttt{Dist}[v],P:\texttt{Pred}[v]</math>

點	<math>v_1</math>	<math>v_2</math>	<math>v_3</math>	<math>v_4</math>
	<math>D/P</math>	<math>D/P</math>	<math>D/P</math>	<math>D/P</math>
初始化	<math>0/\texttt{null}</math>	<math>\infty/\texttt{null}</math>	<math>\infty/\texttt{null}</math>	<math>\infty/\texttt{null}</math>
循環第一次	<math>0/\texttt{null}</math>	<math>-1/v_1</math>	<math>3/v_1</math>	<math>\infty/\texttt{null}</math>
循環第二次	<math>0/\texttt{null}</math>	<math>-1/v_1</math>	<math>3/v_1</math>	<math>2/v_2</math>
循環第三次	<math>0/\texttt{null}</math>	<math>-1/v_1</math>	<math>1/v_4</math>	<math>2/v_2</math>