本页使用了标题或全文手工转换

贝尔曼-福特算法

维基百科,自由的百科全书
(重定向自SPFA算法
跳转至: 导航搜索
贝尔曼-福特算法
分类 单源最短路径问题(针对带权有向图)
数据结构
最坏时间复杂度
空间复杂度

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

算法[编辑]

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

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

贝尔曼-福特算法的最多运行O(|V|·|E|)次,|V|和|E|分别是节点和边的数量)。

伪代码表示[编辑]

procedure BellmanFord(list vertices, list edges, vertex source)
   // 该实现读入边和节点的列表,并向两个数组(distance和predecessor)中写入最短路径信息

   // 步骤1:初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // 步骤2:重复对每一条边进行松弛操作
   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

   // 步骤3:检查负权环
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "图包含了负权环"

原理[编辑]

松弛[编辑]

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

负边权操作[编辑]

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

负权环判定[编辑]

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

优化[编辑]

循环的提前跳出[编辑]

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

队列优化[编辑]

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

Pascal语言示例

 1 Begin
 2   initialize-single-source(G,s);
 3   initialize-queue(Q);
 4   enqueue(Q,s);
 5   while not empty(Q) do 
 6     begin
 7       u:=dequeue(Q);
 8       for each vadj[u] do 
 9         begin
10           tmp:=d[v];
11           relax(u,v);
12           if (tmp<>d[v]) and (not v in Q) then
13             enqueue(Q,v);
14         end;
15     end;
16 End;

C++语言示例

 1 int SPFA(int s) {
 2 	queue<int> q;
 3 	bool inq[maxn] = {false};
 4 	for(int i = 1; i <= N; i++) dis[i] = 2147483647;
 5 	dis[s] = 0;
 6 	q.push(s); inq[s] = true;
 7 	while(!q.empty()) {
 8 		int x = q.front(); q.pop();
 9 		inq[x] = false;
10 		for(int i = front[x]; i !=0 ; i = e[i].next) {
11 			int k = e[i].v;
12 			if(dis[k] > dis[x] + e[i].w) {
13 				dis[k] = dis[x] + e[i].w;
14 				if(!inq[k]) {
15 					inq[k] = true;
16 					q.push(k);
17 				}
18 			}
19 		}
20 	}
21 	for(int i =  1; i <= N; i++) cout << dis[i] << ' ';
22 	cout << endl;
23 	return 0;
24 }

样例[编辑]

例: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

参考文献[编辑]