-
SPFA算法
鎖定
SPFA 算法是 Bellman-Ford算法 的隊列優化算法的別稱，通常用於求含負權邊的單源最短路徑，以及判負權環。SPFA 最壞情況下時間複雜度和樸素 Bellman-Ford 相同，為 O(VE)。
- 中文名
- 貝爾曼-福特算法的隊列優化形式
- 外文名
- Bellman-Ford using queue optimization
- 簡 稱
- SPFA
- 全 稱
- Shortest Path Faster Algorithm
- 引進中國者
- 段凡丁
SPFA算法原理及證明
最短路問題
為了避免最壞情況的出現，在正權圖上應使用效率更高的Dijkstra算法。
若給定的圖存在負權邊，類似Dijkstra算法等算法便沒有了用武之地，SPFA算法便派上用場了。簡潔起見，我們約定加權有向圖G不存在負權迴路，即最短路徑一定存在。用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行鬆弛操作，直至隊列空為止。
定理：只要最短路徑存在，上述SPFA算法必定能求出最小值。證明：每次將點放入隊尾，都是經過鬆弛操作達到的。換言之，每次的優化將會有某個點v的最短路徑估計值d[v]變小。所以算法的執行會使d越來越小。由於我們假定圖中不存在負權迴路，所以每個結點都有最短路徑值。因此，算法不會無限執行下去，隨着d值的逐漸變小，直到到達最短路徑值時，算法結束，這時的最短路徑估計值就是對應結點的最短路徑值。
實際上，如果一個點進入隊列達到n次，則表明圖中存在負環，沒有最短路徑。
對SPFA的一個很直觀的理解就是由無權圖的BFS轉化而來。在無權圖中，BFS首先到達的頂點所經歷的路徑一定是最短路(也就是經過的最少頂點數)，所以此時利用數組記錄節點訪問可以使每個頂點只進隊一次，但在帶權圖中，最先到達的頂點所計算出來的路徑不一定是最短路。一個解決方法是放棄數組，此時所需時間自然就是指數級的，所以我們不能放棄數組，而是在處理一個已經在隊列中且當前所得的路徑比原來更好的頂點時，直接更新最優解。
SPFA算法有四個優化策略：堆優化、棧優化、SLF和LLL。
- 堆優化：將隊列換成堆，與 Dijkstra 的區別是允許一個點多次入堆。在有負權邊的圖可能被卡成指數級複雜度。
- SLF：Small Label First 策略，設要加入的節點是j，隊首元素為i，若dist(j)＜dist(i)，則將j插入隊首，否則插入隊尾；
- LLL：Large Label Last 策略，設隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)＞x則將i插入到隊尾，查找下一元素，直到找到某一i使得dist(i)＜=x，則將i出隊進行鬆弛操作。
SLF 和 LLL 優化在隨機數據上表現優秀，但是在正權圖上最壞情況為 O(VE)，在負權圖上最壞情況為達到指數級複雜度。
SPFA算法代碼形式
ProcedureSPFA; 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;
C++代碼
#include<iostream>
#include<vector>
#include<list>
using namespace std;
struct Edge
{
int to,len;
};
bool spfa(const int &beg,//出發點
const vector<list<Edge> > &adjlist,//鄰接表，通過傳引用避免拷貝
vector<int> &dist,//出發點到各點的最短路徑長度
vector<int> &path)//路徑上到達該點的前一個點
//沒有負權迴路返回0
//福利：這個函數沒有調用任何全局變量，可以直接複製！
{
const int INF=0x7FFFFFFF,NODE=adjlist.size();//用鄰接表的大小傳遞頂點個數，減少參數傳遞
dist.assign(NODE,INF);//初始化距離為無窮大
path.assign(NODE,-1);//初始化路徑為未知
list<int> que(1,beg);//處理隊列
vector<int> cnt(NODE,0);//記錄各點入隊次數，用於判斷負權迴路
vector<bool> flag(NODE,0);//標誌數組，判斷是否在隊列中
dist[beg]=0;//出發點到自身路徑長度為0
cnt[beg]=flag[beg]=1;//入隊並開始計數
while(!que.empty())
{
const int now=que.front();
que.pop_front();
flag[now]=0;//將當前處理的點出隊
for(list<Edge>::const_iterator//用常量迭代器遍歷鄰接表
i=adjlist[now].begin(); i!=adjlist[now].end(); ++i)
if(dist[i->to]>dist[now]+i->len)//不滿足三角不等式
{
dist[i->to]=dist[now]+i->len;//更新
path[i->to]=now;//記錄路徑
if(!flag[i->to])//若未在處理隊列中
{
if(NODE==++cnt[i->to])return 1;//計數後出現負權迴路
if(!que.empty()&&dist[i->to]<dist[que.front()])//隊列非空且優於隊首（SLF）
que.push_front(i->to);//放在隊首
else que.push_back(i->to);//否則放在隊尾
flag[i->to]=1;//入隊
}
}
}
return 0;
}
int main()
{
int n_num,e_num,beg;//含義見下
cout<<"輸入點數、邊數、出發點：";
cin>>n_num>>e_num>>beg;
vector<list<Edge> > adjlist(n_num,list<Edge>());//默認初始化鄰接表
for(int i=0,p; i!=e_num; ++i)
{
Edge tmp;
cout<<"輸入第"<<i+1<<"條邊的起點、終點、長度：";
cin>>p>>tmp.to>>tmp.len;
adjlist[p].push_back(tmp);
}
vector<int> dist,path;//用於接收最短路徑長度及路徑各點
if(spfa(beg,adjlist,dist,path))cout<<"圖中存在負權迴路\n";
else for(int i=0; i!=n_num; ++i)
{
cout<<beg<<"到"<<i<<"的最短距離為"<<dist[i]<<"，反向打印路徑：";
for(int w=i; path[w]>=0; w=path[w])cout<<w<<"<-";
cout<<beg<<'\n';
}
}pascal代碼
const
maxp=10000;{最大結點數}
var{變量定義}
p,c,s,t:longint;{p,結點數;c,邊數;s:起點;t:終點}
a,b:array[1..maxp,0..maxp]of longint;{a[x,y]存x,y之間邊的權;b[x,c]存與x相連的第c個邊的另一個結點y}
d,m:array[1..maxp]of integer;{d:隊列,m:入隊次數標記}
v:array[1..maxp]of boolean;{是否入隊的標記}
dist:array[1..maxp]of longint;{到起點的最短路}
head,tail:longint;{隊首/隊尾指針}
procedure init;
var
i,x,y,z:longint;
begin
read(p,c);
for i:=1 to c do begin
readln(x,y,z);{x,y:一條邊的兩個結點;z:這條邊的權值}
inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z;{b[x,0]：以x為一個結點的邊的條數}
inc(b[y,0]);b[y,b[y,0]]:=x;a[y,x]:=z;
end;
readln(s,t);{讀入起點與終點}
end;
procedure spfa(s:longint);{SPFA}
var
i,j,now:longint;
begin
fillchar(d,sizeof(d),0);
fillchar(v,sizeof(v),false);
for j:=1 to p do dist[j]:=maxlongint;
dist[s]:=0; v[s]:=true; d[1]:=s; {隊列的初始狀態,s為起點}
head:=1; tail:=1;
while head<=tail do{隊列不空}
begin
now:=d[head];{取隊首元素}
for i:=1 to b[now,0] do
if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then
begin
dist[b[now,i]]:=dist[now]+a[now,b[now,i]];{修改最短路}
if not v[b[now,i]] then{擴展結點入隊}
begin
inc(m[b[now,i]]);
if m[b[now,i]]=p then begin writeln('no way');halt;end;
{同一節點入隊次數超過p，存在負環}
inc(tail);
d[tail]:=b[now,i];
v[b[now,i]]:=true;
end;
end;
v[now]:=false;{釋放結點，一定要釋放掉，因為這節點有可能下次用來鬆弛其它節點}
inc(head);{出隊}
end;
end;
procedure print;
begin
writeln(dist[t]);
end;
begin
init;
spfa(s);
print;
end.SPFA算法比較
SPFA算法解決實際問題
2016年秋季大學先修課考試 F
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
#include<queue>
#include<stack>
using namespace std;
const int MAXN=200+10;
queue<int>q;
int n,m,p,h[MAXN][MAXN]={0},X,Y;
bool yan[MAXN][MAXN];
int main()
{
int T;
cin>>T;
while(T--)
{
memset(yan,0,sizeof(yan));
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>h[i][j];
cin>>X>>Y>>p;
while(p--)
{
int a,b;
cin>>a>>b;
q.push(a*MAXN+b);
yan[a][b]=true;
}
while(!q.empty())
{
int x=q.front(),y;
q.pop();
y=x%MAXN,x/=MAXN;
if(x+1<=n)
if(h[x+1][y]<h[x][y])
h[x+1][y]=h[x][y],yan[x+1][y]=true,q.push((x+1)*MAXN+y);
if(x-1>0)
if(h[x-1][y]<h[x][y])
h[x+1][y]=h[x][y],yan[x-1][y]=true,q.push((x-1)*MAXN+y);
if(y<=m)
if(h[x][y+1]<h[x][y])
h[x][y+1]=h[x][y],yan[x][y+1]=true,q.push(x*MAXN+y+1);
if(y>0)
if(h[x][y-1]<h[x][y])
h[x][y+1]=h[x][y],yan[x][y-1]=true,q.push(x*MAXN+y-1);
}
if(yan[X][Y])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
//system("pause");
return 0;
}
poj 1502:MPI Maelstrom
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
int x,y,d,next;
};
int num=0;
node v[11100];
int first[105];
int n;
int q[105];
int f[105];
bool p[105];
int start=1,end=2;
char map[105][5055];
void connect(int x,int y,int d)
{
num++;
v[num].x=x;v[num].y=y;v[num].d=d;
v[num].next=first[x];first[x]=num;
return;
}
int main()
{
int temp;
int ans=0;
memset(first,0,sizeof(first));
memset(q,0,sizeof(q)); q[1]=1;
memset(f,63,sizeof(f)); temp=f[1];f[1]=0;
memset(p,false,sizeof(p)); p[1]=true;
scanf ("%d\n",&n);
for (int i=1;i<n;i++)
{
int x=(i+1),y=1,d=0;
gets(map[i]);
for (int j=0;j<strlen(map[i]);j++)
{
if (map[i][j]!=' ' && map[i][j]!='x') {d*=10;d+=(map[i][j]-'0');}
if (map[i][j]==' ' || j==strlen(map[i])-1)
{
if (map[i][j-1]!='x' && map[i][j]!='x')
{
connect(y,x,d);
connect(x,y,d);
}
d=0;y++;
}
}
}
while (start!=end)
{
int x=q[start];
for (int i=first[x];i!=0;i=v[i].next)
{
int y=v[i].y;
if (f[y]>f[x]+v[i].d)
{
f[y]=f[x]+v[i].d;
if (p[y]==false)
{
q[end]=y;
p[y]=true;
end++;
if (end>n) end=1;
}
}
}
p[x]=false;
start++;
if (start>n) start=1;
}
for (int i=1;i<=n;i++)
{
if (f[i]!=temp && f[i]>ans) ans=f[i];
}
printf ("%d",ans);
return 0;
}
