查看“︁贝尔曼-福特算法”︁的源代码

{{noteTA
|G1=IT
}}
{{Infobox Algorithm
|class=[[最短路径问题]]（针对带权有向图）
|image=
|caption = 
|data=[[图]]
|time=<math>O \left (|V| |E|\right )</math>
|space=<math>O (|V|)</math>
}}
{{图搜索算法}}
'''贝尔曼-福特算法'''（{{lang-en|Bellman–Ford algorithm}}），求解单源[[最短路径]]问题的一种[[算法]]，由[[理查德·貝尔曼]]和[[小萊斯特·倫道夫·福特]]创立。有时候这种算法也被称为'''貝爾曼-福特-摩爾算法'''（Bellman–Ford–Moore algorithm），因为[[愛德華·F·摩爾]]也为这个算法的发展做出了贡献。它的原理是对图进行<math> |V|-1</math>次松弛操作，得到所有可能的最短路径。其优于[[戴克斯特拉算法]]的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达<math>O (|V| |E|)</math>。但算法可以进行若干种优化，提高了效率。

==算法==
[[File:Bellman-Ford worst-case example.svg|thumb|在这个图中，假设A是起点，并且边以最坏的顺序处理，从右到左，需要<math>|V|-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>分别是节点和边的数量）。

===偽代碼===
 '''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)
    // 讀入邊和節點的列表 
    // 初始化圖distance為∞，predecessor為空
    '''for each''' vertex v '''in''' vertices:
        '''if''' v '''is''' source '''then''' distance[v] := 0
        '''else''' distance[v] := '''infinity'''
        predecessor[v] := '''null'''
    // 對所有節點
    <!-- The outer loop iterates |V|-1 times. See, e.g, CLRS Ch. 24.1.  The value of i is unused. -->
    '''for''' i '''from''' 1 '''to''' size(vertices)-1:
         //檢查每條邊
        '''for each''' edge (u, v) '''with''' weight w '''in''' edges:
            '''if''' distance[u] + w < distance[v]:
                distance[v] := distance[u] + w
                predecessor[v] := u
 
    // 檢查是否有負權重的迴路
    '''for each''' edge (u, v) '''with''' weight w '''in''' edges:
        '''if''' distance[u] + w < distance[v]:
            '''error''' "圖包含負權重的迴路"

==原理==
===循环===
每次循环操作实际上是对相邻节点的访问，第<math>n</math>次循环操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过<math>|V|-1</math>条边，所以可知贝尔曼-福特算法所得为最短路径。

===负边权操作===
与[[戴克斯特拉演算法]]不同的是，戴克斯特拉演算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

===负权环判定===
因为负权环可以无限制的降低总花费，所以如果发现第<math>n</math>次操作仍可降低花销，就一定存在负权环。
==尋找負迴路==
當使用這個算法尋找最短路徑時，有負迴路會使算法找不到正確的答案。但是，由於在找到負迴路後會中止算法，所以可以被用來尋找目標，例如在網路流分析中的消圈演算法(Cycle Cancellation Algorithms)
==优化==
===循环的提前跳出===
在实际操作中，贝尔曼-福特算法经常会在未达到<math>|V| - 1</math>次前就出解，<math>|V| - 1</math>其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

===队列优化===
{{main|最短路径快速算法}}

西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为<math>O(k|E|)</math>，<math>k</math>是个比较小的系数，<ref>{{Cite web |url=http://www.cnki.com.cn/Article/CJFDTotal-XNJT402.015.htm |title=存档副本 |accessdate=2013-07-17 |archive-date=2016-03-04 |archive-url=https://web.archive.org/web/20160304114901/http://www.cnki.com.cn/Article/CJFDTotal-XNJT402.015.htm |dead-url=no }}</ref>但该结论被证明不适于于所有情况。{{来源请求|reason=暂无可靠来源}}

'''Pascal语言示例'''

<syntaxhighlight lang="pascal" line="1">
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;
</syntaxhighlight>'''C++语言示例'''<syntaxhighlight lang="c++" line="1">
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;
}
</syntaxhighlight>

==样例==
例：
:<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>
{| border="1" cellspacing="0" cellpadding="5" align="center"
! 点
! <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>
|}

==参考文献==
<div class="references-small">
<references></references>
</div>

{{算法}}

[[Category:图算法]]
[[Category:多项式时间问题]]
[[Category:带有伪代码示例的条目]]
[[Category:带有代码示例的条目]]