B-F
適用條件&范圍
- 單源最短路徑(從源點s到其它所有頂點v);
- 有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖);
- 邊權(quán)可正可負(如有負權(quán)回路輸出錯誤提示);
- 差分約束系統(tǒng);
算法描述
- 對每條邊進行|V|-1次Relax ( 就是松弛操作 )操作;
- 如果存在(u,v)∈E使得dis[u]+w<dis[v],則存在負權(quán)回路;否則dis[v]即為s到v的最短距離,pre[v]為前驅(qū)。
For i:=1 to |V|-1 do //v為頂點數(shù)
For 每條邊(u,v)∈E do //對每條邊進行遍歷
Relax(u,v,w);
For每條邊(u,v)∈E do
If dis[u]+w<dis[v] Then Exit(False)
時空復雜度
算法時間復雜度O(VE)。因為算法簡單，適用范圍又廣，雖然復雜度稍高，仍不失為一個很實用的算法。
算法的改進---> SPFA
算法簡介
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種隊列實現(xiàn)，減少了不必要的冗余計算。也有人說SPFA本來就是Bellman-Ford算法，現(xiàn)在廣為流傳的Bellman-Ford算法實際上是山寨版。
算法流程
算法大致流程是用一個隊列來進行維護。 初始時將源加入隊列。 每次從隊列中取出一個元素，并對所有與他相鄰的點進行松弛，若某個相鄰的點松弛成功，則將其入隊。 直到隊列為空時算法結(jié)束。
這個算法，簡單的說就是隊列優(yōu)化的bellman-ford,利用了每個點不會更新次數(shù)太多的特點發(fā)明的此算法
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的時間復雜度內(nèi)求出源點到其他所有點的最短路徑，可以處理負邊。SPFA的實現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡單：
設(shè)Dist代表S到I點的當前最短距離，F(xiàn)a代表S到I的當前最短路徑中I點之前的一個點的編號。開始時Dist全部為+∞，只有Dist[S]=0，F(xiàn)a全部為0。
維護一個隊列，里面存放所有需要進行迭代的點。初始時隊列中只有一個點S。用一個布爾數(shù)組記錄每個點是否處在隊列中。
每次迭代，取出隊頭的點v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長度為len，判斷Dist[v]+len是否小于Dist[u]，若小于則改進Dist[u]，將Fa[u]記為v，并且由于S到u的最短距離變小了，有可能u可以改進其它的點，所以若u不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空，也就是S到所有的最短距離都確定下來，結(jié)束算法。若一個點入隊次數(shù)超過n，則有負權(quán)環(huán)。
SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復迭代下去。設(shè)一個點用來作為迭代點對其它點進行改進的平均次數(shù)為k，有辦法證明對于通常的情況，k在2左右
算法代碼
Procedure SPFA;
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;
procedure spfa;
begin
fillchar(q,sizeof(q),0); h:=0; t:=0;//隊列
fillchar(v,sizeof(v),false);//v[i]判斷i是否在隊列中
for i:=1 to n do
dist[i]:=maxint;//初始化最小值
inc(t);
q[t]:=1;
v[1]:=true;
dist[1]:=0;//這里把1作為源點
while h<>t do
begin
h:=(h mod n)+1;
x:=q[h];
v[x]:=false;
for i:=1 to n do
if (cost[x,i]>0) and (dist[x]+cost[x,i]<dist[i]) then
begin
dist[i]:=dist[x]+cost[x,i];
if not(v[i]) then
begin
t:=(t mod n)+1;
q[t]:=i;
v[i]:=true;
end;
end;
end;
end;void SPFA(void)//好久以前寫的……今天丟上來……話說我都不記得SPFA怎么寫了……囧……ms存圖是矩陣……嗯嗯
{
int i;
queue list;
list.insert(s);
for(i=1;i<=n;i++)
{
if(s==i)
continue;
dist[i]=map[s][i];
way[i]=s;
if(dist[i])
list.insert(i);
}
int p;
while(!list.empty())
{
p=list.fire();
for(i=1;i<=n;i++)
if(map[p][i]&&(dist[i]>dist[p]+map[p][i]||!dist[i])&&i!=s)
{
dist[i]=dist[p]+map[p][i];
way[i]=p;
if(!list.in(i))
list.insert(i);
}
}
}