Bellman-Ford算法与另一个非常著名的Dijkstra算法一样，用于求解单源点最短路径问题。Bellman-ford算法除了可求解边权均非负的问题外，还可以解决存在负权边的问题（意义是什么，好好思考），而Dijkstra算法只能处理边权非负的问题，因此 Bellman-Ford算法的适用面要广泛一些。但是，原始的Bellman-Ford算法时间复杂度为 O（VE）,比Dijkstra算法的时间复杂度高，所以常常被众多的大学算法教科书所忽略，就连经典的《算法导论》也只介绍了基本的Bellman-Ford算法，在国内常见的基本信息学奥赛教材中也均未提及，因此该算法的知名度与被掌握度都不如Dijkstra算法。事实上，有多种形式的Bellman-Ford算法的优化实现。这些优化实现在时间效率上得到相当提升，例如近一两年被热捧的SPFA（Shortest-Path Faster Algoithm 更快的最短路径算法）算法的时间效率甚至由于Dijkstra算法，因此成为信息学奥赛选手经常讨论的话题。然而，限于资料匮乏，有关Bellman-Ford算法的诸多问题常常困扰奥赛选手。如：该算法值得掌握么？怎样用编程语言具体实现？有哪些优化？与SPFA算法有关系么？本文试图对Bellman-Ford算法做一个比较全面的介绍。给出几种实现程序，从理论和实测两方面分析他们的时间复杂度，供大家在备战省选和后续的noi时参考。
Bellman-Ford算法思想
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。
Bellman-Ford算法流程分为三个阶段：
（1） 初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
（2） 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
（3） 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
算法描述如下：
1 G:图G
2 E(G):边的集合
3 S: 源顶点
4 Dis[i]:表示s到i的最短距离,初始为+∞
5 D[s]=0;
6 for (int i=0;i<|v|-1;i++)
7 for each (u,v)∈E(G)
8 if(dis[u]+w(u,v)<dis[v]
9 dis[v]=dis[u]+w(u,v);
10 for each (u,v)∈E(G)
11 if(d[v]>d[u]+w(u,v)
12 return false;//返回false,说明存在负权回路
13 return true;
14
下面给出描述性证明：
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
Bellman-Ford的队列实现SPFA
算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。
SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右
1 图G
2 队列 queue<int> q;
3 Inque[i] 标记i是否在队列里，初始所有为false
4 S: 源顶点
5 Dis[i]:表示s到i的最短距离,初始为+∞
6
7 Dis[s]=0;
8 q.push(s);
9 inque[s]=true;
10 while(q.size()>0)
11 {
12 Int t=q.front();
13 q.pop();
14 inque[t]=false;
15 for t’s adjacent vertex v
16 if(dis[t]+w(t,v)<dis[v])
17 {
18 Dis[v]=dis[t]+w(t,v);
19 If(!inque[v])
20 {
21 q.push(v);
22 inque[v]=true;
23 }
24 }
25
26 }
27
USACO 3.2 Sweet Butter
Sweet Butter
Greg Galperin -- 2001
Farmer John has discovered the secret to making the sweetest butter in all of Wisconsin: sugar. By placing a sugar cube out in the pastures, he knows the N (1 <= N <= 500) cows will lick it and thus will produce super-sweet butter which can be marketed at better prices. Of course, he spends the extra money on luxuries for the cows.
FJ is a sly farmer. Like Pavlov of old, he knows he can train the cows to go to a certain pasture when they hear a bell. He intends to put the sugar there and then ring the bell in the middle of the afternoon so that the evening's milking produces perfect milk.
FJ knows each cow spends her time in a given pasture (not necessarily alone). Given the pasture location of the cows and a description of the paths the connect the pastures, find the pasture in which to place the sugar cube so that the total distance walked by the cows when FJ rings the bell is minimized. FJ knows the fields are connected well enough that some solution is always possible.
PROGRAM NAME: butter
INPUT FORMAT
- Line 1: Three space-separated integers: N, the number of pastures: P (2 <= P <= 800), and the number of connecting paths: C (1 <= C <= 1,450). Cows are uniquely numbered 1..N. Pastures are uniquely numbered 1..P.
- Lines 2..N+1: Each line contains a single integer that is the pasture number in which a cow is grazing. Cow i's pasture is listed on line i+1.
- Lines N+2..N+C+1: Each line contains three space-separated integers that describe a single path that connects a pair of pastures and its length. Paths may be traversed in either direction. No pair of pastures is directly connected by more than one path. The first two integers are in the range 1..P; the third integer is in the range (1..225).
SAMPLE INPUT (file butter.in)
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
INPUT DETAILS
This diagram shows the connections geometrically:
OUTPUT FORMAT
- Line 1: A single integer that is the minimum distance the cows must walk to a pasture with a sugar cube.
SAMPLE OUTPUT (file butter.out)
8
OUTPUT DETAILS:
Putting the cube in pasture 4 means: cow 1 walks 3 units; cow 2 walks 5
units; cow 3 walks 0 units -- a total of 8.
解答:
这道题直接用一般的Dijkstra算法O(P2),一共调用P次Dijkstra,总体复杂度O(P3),p=800,肯定超时,在这里用SPFA算法,O(k*c),k是2左右的常数,
调用p次,整体复杂度O(p*c*k).在0.2秒可以得出解.附原码
/*
ID: kuramaw1
PROG: butter
LANG: C++
*/
#include <fstream>
#include <queue>
using std::ifstream;
using std::ofstream;
using std::queue;
using std::endl;
using std::vector;
#define MAX_EDGE 1451
#ifndef INT_MAX
#define INT_MAX 2147483647
#endif
struct graph
{
struct Edge
{
short n; // next adjacent edge
short v; // to which vertex
short c; // weight
Edge(const short _n=-1,const short _v=-1,const short _c=0):n(-n),v(_v),c(-c)
{
}
Edge(const Edge &e):n(e.n),v(e.v),c(e.c)
{
}
Edge & operator =(const Edge &e)
{
n=e.n;
v=e.v;
c=e.c;
return *this;
}
};
struct Ver
{
short w;
short e;//frist e
Ver(const short _w=0,const short _e=-1):w(_w),e(_e)
{
}
Ver(const Ver &v):w(v.w),e(v.e)
{
}
Ver & operator =(const Ver &v)
{
w=v.w;
e=v.e;
return *this;
}
};
typedef std::vector<Edge> EdgeSet;
typedef std::vector<Ver> VertSet;
VertSet _V;
EdgeSet _E;
// interfaces
inline void Reset(const short &n)
{
_V.resize(n);
_E.clear();
_E.reserve(MAX_EDGE);
}
inline void IncVetWei(const short &i)
{
_V[i].w++;
}
inline void InsertEdge(short u, short v, short c)
{
Edge e;
e.v = v, e.c = c, e.n = _V[u].e;
_V[u].e = _E.size();
_E.push_back(e);
e.v = u, e.c = c, e.n = _V[v].e;
_V[v].e = _E.size();
_E.push_back(e);
}
int short_dis_sum(const short &s)
{
vector<int> dis;
queue<short> q;
vector<bool> b_in_que;
dis.resize(_V.size(),INT_MAX);
b_in_que.resize(_V.size(),false);
q.push(s);
dis[s]=0;
b_in_que[s]=true;
while(q.size()>0)
{
short t=q.front();
q.pop();
b_in_que[t]=false;
short e=_V[t].e;
while(e!=-1)
{
Edge &edge=_E[e];
if(dis[t]+edge.c<dis[edge.v])
{
dis[edge.v]=dis[t]+edge.c;
if(!b_in_que[edge.v])
{
q.push(edge.v);
b_in_que[edge.v]=true;
}
}
e=edge.n;
}
}
int sum(0);
for(short i=0;i<dis.size();i++)
if(_V[i].w>0)
{
sum+=_V[i].w*dis[i];
}
return sum;
}
};
graph g;
short n,p,c;
int main()
{
ifstream in("butter.in");
in>>n>>p>>c;
g.Reset(p);
for(short i=0;i<n;i++)
{
short v;
in>>v;
g.IncVetWei(v-1);
}
for(short i=0;i<c;i++)
{
short u,v,w;
in>>u>>v>>w;
g.InsertEdge(u-1,v-1,w);
}
in.close();
int min_dis=INT_MAX;
for(int i=0;i<p;i++)
{
int dis=g.short_dis_sum(i);
if(dis<min_dis)
min_dis=dis;
}
//out
ofstream out("butter.out");
out<<min_dis<<endl;
out.close();
}
posted on 2009-08-12 21:49
kuramawzw 阅读(1000)
评论(0) 编辑 收藏 引用 所属分类:
图论