Bellman-Ford算法與另一個(gè)非常著名的Dijkstra算法一樣，用于求解單源點(diǎn)最短路徑問(wèn)題。Bellman-ford算法除了可求解邊權(quán)均非負(fù)的問(wèn)題外，還可以解決存在負(fù)權(quán)邊的問(wèn)題（意義是什么，好好思考），而Dijkstra算法只能處理邊權(quán)非負(fù)的問(wèn)題，因此 Bellman-Ford算法的適用面要廣泛一些。但是，原始的Bellman-Ford算法時(shí)間復(fù)雜度為 O（VE）,比Dijkstra算法的時(shí)間復(fù)雜度高，所以常常被眾多的大學(xué)算法教科書(shū)所忽略，就連經(jīng)典的《算法導(dǎo)論》也只介紹了基本的Bellman-Ford算法，在國(guó)內(nèi)常見(jiàn)的基本信息學(xué)奧賽教材中也均未提及，因此該算法的知名度與被掌握度都不如Dijkstra算法。事實(shí)上，有多種形式的Bellman-Ford算法的優(yōu)化實(shí)現(xiàn)。這些優(yōu)化實(shí)現(xiàn)在時(shí)間效率上得到相當(dāng)提升，例如近一兩年被熱捧的SPFA（Shortest-Path Faster Algoithm 更快的最短路徑算法）算法的時(shí)間效率甚至由于Dijkstra算法，因此成為信息學(xué)奧賽選手經(jīng)常討論的話題。然而，限于資料匱乏，有關(guān)Bellman-Ford算法的諸多問(wèn)題常常困擾奧賽選手。如：該算法值得掌握么？怎樣用編程語(yǔ)言具體實(shí)現(xiàn)？有哪些優(yōu)化？與SPFA算法有關(guān)系么？本文試圖對(duì)Bellman-Ford算法做一個(gè)比較全面的介紹。給出幾種實(shí)現(xiàn)程序，從理論和實(shí)測(cè)兩方面分析他們的時(shí)間復(fù)雜度，供大家在備戰(zhàn)省選和后續(xù)的noi時(shí)參考。
Bellman-Ford算法思想
Bellman-Ford算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點(diǎn)最短路徑問(wèn)題。對(duì)于給定的帶權(quán)（有向或無(wú)向）圖 G=（V,E），其源點(diǎn)為s，加權(quán)函數(shù) w是 邊集 E 的映射。對(duì)圖G運(yùn)行Bellman-Ford算法的結(jié)果是一個(gè)布爾值，表明圖中是否存在著一個(gè)從源點(diǎn)s可達(dá)的負(fù)權(quán)回路。若不存在這樣的回路，算法將給出從源點(diǎn)s到 圖G的任意頂點(diǎn)v的最短路徑d[v]。
Bellman-Ford算法流程分為三個(gè)階段：
（1） 初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值 d[v] ←+∞, d[s] ←0;
（2） 迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）
（3） 檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在 d[v]中。
算法描述如下：
1 G:圖G
2 E(G):邊的集合
3 S: 源頂點(diǎn)
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,說(shuō)明存在負(fù)權(quán)回路
13 return true;
14
下面給出描述性證明：
首先指出，圖的任意一條最短路徑既不能包含負(fù)權(quán)回路，也不會(huì)包含正權(quán)回路，因此它最多包含|v|-1條邊。
其次，從源點(diǎn)s可達(dá)的所有頂點(diǎn)如果 存在最短路徑，則這些最短路徑構(gòu)成一個(gè)以s為根的最短路徑樹(shù)。Bellman-Ford算法的迭代松弛操作，實(shí)際上就是按頂點(diǎn)距離s的層次，逐層生成這棵最短路徑樹(shù)的過(guò)程。
在對(duì)每條邊進(jìn)行1遍松弛的時(shí)候，生成了從s出發(fā)，層次至多為1的那些樹(shù)枝。也就是說(shuō)，找到了與s至多有1條邊相聯(lián)的那些頂點(diǎn)的最短路徑；對(duì)每條邊進(jìn)行第2遍松弛的時(shí)候，生成了第2層次的樹(shù)枝，就是說(shuō)找到了經(jīng)過(guò)2條邊相連的那些頂點(diǎn)的最短路徑……。因?yàn)樽疃搪窂阶疃嘀话?/span>|v|-1 條邊，所以，只需要循環(huán)|v|-1 次。
每實(shí)施一次松弛操作，最短路徑樹(shù)上就會(huì)有一層頂點(diǎn)達(dá)到其最短距離，此后這層頂點(diǎn)的最短距離值就會(huì)一直保持不變，不再受后續(xù)松弛操作的影響。（但是，每次還要判斷松弛，這里浪費(fèi)了大量的時(shí)間，怎么優(yōu)化？單純的優(yōu)化是否可行？）
如果沒(méi)有負(fù)權(quán)回路，由于最短路徑樹(shù)的高度最多只能是|v|-1，所以最多經(jīng)過(guò)|v|-1遍松弛操作后，所有從s可達(dá)的頂點(diǎn)必將求出最短距離。如果 d[v]仍保持 +∞，則表明從s到v不可達(dá)。
如果有負(fù)權(quán)回路，那么第 |v|-1 遍松弛操作仍然會(huì)成功，這時(shí)，負(fù)權(quán)回路上的頂點(diǎn)不會(huì)收斂。
Bellman-Ford的隊(duì)列實(shí)現(xiàn)SPFA
算法大致流程是用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)。初始時(shí)將源加入隊(duì)列。每次從隊(duì)列中取出一個(gè)元素，并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個(gè)相鄰的點(diǎn)松弛成功，則將其入隊(duì)。直到隊(duì)列為空時(shí)算法結(jié)束。
這個(gè)算法，簡(jiǎn)單的說(shuō)就是隊(duì)列優(yōu)化的bellman-ford,利用了每個(gè)點(diǎn)不會(huì)更新次數(shù)太多的特點(diǎn)發(fā)明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。SPFA的實(shí)現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡(jiǎn)單：
設(shè)Dist代表S到I點(diǎn)的當(dāng)前最短距離，Fa代表S到I的當(dāng)前最短路徑中I點(diǎn)之前的一個(gè)點(diǎn)的編號(hào)。開(kāi)始時(shí)Dist全部為+∞，只有Dist[S]=0，Fa全部為0。
維護(hù)一個(gè)隊(duì)列，里面存放所有需要進(jìn)行迭代的點(diǎn)。初始時(shí)隊(duì)列中只有一個(gè)點(diǎn)S。用一個(gè)布爾數(shù)組記錄每個(gè)點(diǎn)是否處在隊(duì)列中。
每次迭代，取出隊(duì)頭的點(diǎn)v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長(zhǎng)度為len，判斷Dist[v]+len是否小于Dist[u]，若小于則改進(jìn)Dist[u]，將Fa[u]記為v，并且由于S到u的最短距離變小了，有可能u可以改進(jìn)其它的點(diǎn)，所以若u不在隊(duì)列中，就將它放入隊(duì)尾。這樣一直迭代下去直到隊(duì)列變空，也就是S到所有的最短距離都確定下來(lái)，結(jié)束算法。若一個(gè)點(diǎn)入隊(duì)次數(shù)超過(guò)n，則有負(fù)權(quán)環(huán)。
SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之后，過(guò)了一段時(shí)間可能本身被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。設(shè)一個(gè)點(diǎn)用來(lái)作為迭代點(diǎn)對(duì)其它點(diǎn)進(jìn)行改進(jìn)的平均次數(shù)為k，有辦法證明對(duì)于通常的情況，k在2左右
1 圖G
2 隊(duì)列 queue<int> q;
3 Inque[i] 標(biāo)記i是否在隊(duì)列里，初始所有為false
4 S: 源頂點(diǎn)
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),一共調(diào)用P次Dijkstra,總體復(fù)雜度O(P3),p=800,肯定超時(shí),在這里用SPFA算法,O(k*c),k是2左右的常數(shù),
調(diào)用p次,整體復(fù)雜度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 閱讀(1054)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論