SPFA算法

SPFA 算法是 Bellman-Ford算法 的佇列最佳化算法的別稱，通常用於求含負權邊的單源最短路徑，以及判負權環。SPFA 最壞情況下複雜度和樸素 Bellman-Ford 相同，為 O(VE)。

基本介紹

• 中文名：貝爾曼-福特算法的佇列最佳化形式
• 外文名：Bellman-Ford using queue optimization
• 簡稱：SPFA
• 全稱：Shortest Path Faster Algorithm
• 引進中國者：段凡丁

原理及證明

SPFA算法的全稱是：Shortest Path Faster Algorithm，是西南交通大學段凡丁於 1994 年發表的論文中的名字。不過，段凡丁的證明是錯誤的，且在 Bellman-Ford 算法提出後不久（1957 年）已有佇列最佳化內容，所以國際上不承認 SPFA 算法是段凡丁提出的。

最短路問題

為了避免最壞情況的出現，在正權圖上應使用效率更高的Dijkstra算法。

若給定的圖存在負權邊，類似Dijkstra算法等算法便沒有了用武之地，SPFA算法便派上用場了。簡潔起見，我們約定加權有向圖G不存在負權迴路，即最短路徑一定存在。用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的佇列用來保存待最佳化的結點，最佳化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的佇列中，就將v點放入隊尾。這樣不斷從佇列中取出結點來進行鬆弛操作，直至佇列空為止。

定理：只要最短路徑存在，上述SPFA算法必定能求出最小值。證明：每次將點放入隊尾，都是經過鬆弛操作達到的。換言之，每次的最佳化將會有某個點v的最短路徑估計值d[v]變小。所以算法的執行會使d越來越小。由於我們假定圖中不存在負權迴路，所以每個結點都有最短路徑值。因此，算法不會無限執行下去，隨著d值的逐漸變小，直到到達最短路徑值時，算法結束，這時的最短路徑估計值就是對應結點的最短路徑值。

實際上，如果一個點進入佇列達到n次，則表明圖中存在負環，沒有最短路徑。

段凡丁論文中的複雜度證明 （O(kE)，k 是小常數）是錯誤的，在此略去。該算法的最壞複雜度為 O(VE)。

對SPFA的一個很直觀的理解就是由無權圖的BFS轉化而來。在無權圖中，BFS首先到達的頂點所經歷的路徑一定是最短路(也就是經過的最少頂點數)，所以此時利用數組記錄節點訪問可以使每個頂點只進隊一次，但在帶權圖中，最先到達的頂點所計算出來的路徑不一定是最短路。一個解決方法是放棄數組，此時所需時間自然就是指數級的，所以我們不能放棄數組，而是在處理一個已經在佇列中且當前所得的路徑比原來更好的頂點時，直接更新最優解。

SPFA算法有兩個最佳化策略SLF和LLL——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 和 LLF 在隨機數據上表現優秀，但是在正權圖上最壞情況為 O(VE)，在負權圖上最壞情況為達到指數級複雜度。

代碼形式

偽代碼

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.

比較

與bfs算法比較，複雜度相對穩定。但在稠密圖中複雜度比迪傑斯特拉算法差。

解決實際問題

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;}