贝尔曼-福特算法

贝尔曼-福特算法（英語：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·貝尔曼（Richard Bellman） 和 萊斯特·福特（英语：Lester Ford） 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行${\displaystyle |V|-1}$次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达${\displaystyle O(|V||E|)}$。但算法可以进行若干种优化，提高了效率。

贝尔曼-福特算法
概况
類別	最短路径问题（针对带权有向图）
資料結構	图
复杂度
最坏时间复杂度	${\displaystyle O\left(|V||E|\right)}$
最优时间复杂度	${\displaystyle \Theta (|E|)}$
空間複雜度	${\displaystyle O(|V|)}$
相关变量的定义

算法

 

在这个图中，假设A是起点，并且边以最坏的顺序处理，从右到左，需要${\displaystyle |V|-1}$ 步或${\displaystyle 4}$ 次计算路径长度。相反地，若边以最优顺序处理，从左到右，算法只需要在一次遍历内完成。

贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共${\displaystyle |V|-1}$ 次，其中${\displaystyle |V|}$ 是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

贝尔曼-福特算法的最多运行${\displaystyle O(|V|\cdot |E|)}$ （大O符号）次，${\displaystyle |V|}$ 和${\displaystyle |E|}$ 分别是节点和边的数量）。

偽代碼

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 // 對每一條邊重複操作 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 "圖包含負權重的回路" 

原理

循环

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

负边权操作

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

负权环判定

因为负权环可以无限制的降低总花费，所以如果发现第${\displaystyle n}$ 次操作仍可降低花销，就一定存在负权环。

尋找負迴路

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

优化

循环的提前跳出

在实际操作中，贝尔曼-福特算法经常会在未达到${\displaystyle |V|-1}$ 次前就出解，${\displaystyle |V|-1}$ 其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

队列优化

主条目：最短路径快速算法

西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为${\displaystyle O(k|E|)}$ ，${\displaystyle k}$ 是个比较小的系数，^[1]但该结论被证明不适于于所有情况。^{[來源請求]}

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; } 

样例

例：

${\displaystyle 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})\}}$ ，${\displaystyle weight(v_{1},v_{2})=-1,weight(v_{1},v_{3})=3,weight(v_{2},v_{4})=3,weight(v_{4},v_{3})=-1}$ 。

运行如表： ${\displaystyle D:{\texttt {Dist}}[v],P:{\texttt {Pred}}[v]}$ 

点	${\displaystyle v_{1}}$	${\displaystyle v_{2}}$	${\displaystyle v_{3}}$	${\displaystyle v_{4}}$
	${\displaystyle D/P}$	${\displaystyle D/P}$	${\displaystyle D/P}$	${\displaystyle D/P}$
初始化	${\displaystyle 0/{\texttt {null}}}$	${\displaystyle \infty /{\texttt {null}}}$	${\displaystyle \infty /{\texttt {null}}}$	${\displaystyle \infty /{\texttt {null}}}$
循环第一次	${\displaystyle 0/{\texttt {null}}}$	${\displaystyle -1/v_{1}}$	${\displaystyle 3/v_{1}}$	${\displaystyle \infty /{\texttt {null}}}$
循环第二次	${\displaystyle 0/{\texttt {null}}}$	${\displaystyle -1/v_{1}}$	${\displaystyle 3/v_{1}}$	${\displaystyle 2/v_{2}}$
循环第三次	${\displaystyle 0/{\texttt {null}}}$	${\displaystyle -1/v_{1}}$	${\displaystyle 1/v_{4}}$	${\displaystyle 2/v_{2}}$

参考文献

1. 存档副本. [2013-07-17]. （原始内容于2016-03-04）.