贝尔曼-福特算法

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

算法

自然语言描述

对有向图$G(V,E)$，用贝尔曼-福特算法求以$V_s$为源点的最短路径的过程：

• 建立$dist[]$，表示目前已知源點到各個節點的最短距離，起始值 $dist[s]=0$，其餘皆為$\infty$。
• 建立$Pred[]$，$Pred[]$表示某节点路径上的父节点，起始值皆為NULL。
• 对$(V_i,V_j) \in E$，比较$dist[V_i]+(V_i,V_j)$和$dist[V_j]$,并将小的赋给$dist[V_j]$，如果修改了$dist[V_j]$则$pred[V_j]=V_i$（松弛操作）
• 重复以上操作$V-1$次
• 再重复操作一次，如$dist[V_j]>dist[V_i]+(V_i,V_j)$,则此图存在负权环。

伪代码表示

BellmanFord(G,s)
 for i = 0 to n-1 do
  dist[i]= ∞
  Pred[i]= 0
 dist[s]=0
 
 for k = 1 to n-1 do
    foreach $(V_i,V_j)$∈$E$ do
      if $dist[V_i]+(V_i,V_j)<dist[V_j]$ do
         $dist[V_j]=dist[V_i]+(V_i,V_j)$
         $Pred[V_j]=V_i$
foreach $(V_i,V_j)$∈$E$ do
      if $dist[V_i]+(V_i,V_j)<dist[V_j]$ do
         return "No Shortest Path"
 return dist[]

原理

松弛

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

负边权操作

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

负权环判定

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

优化

循环的提前跳出

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

队列优化

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的。 松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。复杂度可以降低到O(kE)，k是个比较小的系数(并且在绝大多数的图中，k<=2，然而在一些精心构造的图中可能会上升到很高)

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;

样例

例：V={v1,v2,v3,v4} E={(v1,v2),(v1,v3),(v2,v4),(v4,v3)} weight(v1,v2)=-1 weight(v1,v3)=3 weight(v2,v4)=3 weight(v4,v3)=-1

运行如表： D:Dist[v]，P:Pred[v]

点	v1	v2	v3	v4
	D/P	D/P	D/P	D/P
初始化	0/null	∞/null	∞/null	∞/null
循环第一次	0/null	-1/v1	3/v1	∞/null
循环第二次	0/null	-1/v1	3/v1	2/v2
循环第三次	0/null	-1/v1	1/v4	2/v2