粗略講講SPFA算法的原理，SPFA算法是1994年西安交通大學段凡丁提出

是一種求單源最短路的算法

算法中需要用到的主要變量

int n; ?//表示n個點，從1到n標號

int s,t; ?//s為源點，t為終點

int d[N]; ?//d[i]表示源點s到點i的最短路

int p[N]; ?//記錄路徑（或者說記錄前驅）

queue <int> q; ?//一個隊列，用STL實現，當然可有手打隊列，無所謂

bool vis[N]; ? //vis[i]=1表示點i在隊列中 vis[i]=0表示不在隊列中

?

幾乎所有的最短路算法其步驟都可以分為兩步

1.初始化

2.松弛操作

?

初始化： d數組全部賦值為INF（無窮大）；p數組全部賦值為s（即源點），或者賦值為-1，表示還沒有知道前驅

? ? ? ? ? ? ?然后d[s]=0; ?表示源點不用求最短路徑，或者說最短路就是0。將源點入隊；

　　　　（另外記住在整個算法中有頂點入隊了要記得標記vis數組，有頂點出隊了記得消除那個標記）

隊列+松弛操作

讀取隊頭頂點u，并將隊頭頂點u出隊（記得消除標記）；將與點u相連的所有點v進行松弛操作，如果能更新估計值（即令d[v]變小），那么就更新，另外，如果點v沒有在隊列中，那么要將點v入隊（記得標記），如果已經在隊列中了，那么就不用入隊

以此循環，直到隊空為止就完成了單源最短路的求解

?

SPFA可以處理負權邊

定理: 只要最短路徑存在，上述SPFA算法必定能求出最小值。

證明：

　　每次將點放入隊尾，都是經過松弛操作達到的。換言之，每次的優化將會有某個點v的最短路徑估計值d[v]變小。所以算法的執行會使d越來越小。由于我們假定圖中不存在負權回路，所以每個結點都有最短路徑值。因此，算法不會無限執行下去，隨著d值的逐漸變小，直到到達最短路徑值時，算法結束，這時的最短路徑估計值就是對應結點的最短路徑值。（證畢）

期望的時間復雜度O(ke)， 其中k為所有頂點進隊的平均次數，可以證明k一般小于等于2。

?

判斷有無負環：

　　如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）

?

?

?

SPFA的兩種寫法，bfs和dfs，bfs判別負環不穩定，相當于限深度搜索，但是設置得好的話還是沒問題的，dfs的話判斷負環很快

?

int spfa_bfs(int s)
{queue <int> q;memset(d,0x3f,sizeof(d));d[s]=0;memset(c,0,sizeof(c));memset(vis,0,sizeof(vis));q.push(s);  vis[s]=1; c[s]=1;//頂點入隊vis要做標記，另外要統計頂點的入隊次數int OK=1;while(!q.empty()){int x;x=q.front(); q.pop();  vis[x]=0;//隊頭元素出隊，并且消除標記for(int k=f[x]; k!=0; k=nnext[k]) //遍歷頂點x的鄰接表
        {int y=v[k];if( d[x]+w[k] < d[y]){d[y]=d[x]+w[k];  //松弛if(!vis[y])  //頂點y不在隊內
                {vis[y]=1;    //標記c[y]++;      //統計次數q.push(y);   //入隊if(c[y]>NN)  //超過入隊次數上限，說明有負環return OK=0;}}}}return OK;}

?

int spfa_dfs(int u)
{vis[u]=1;for(int k=f[u]; k!=0; k=e[k].next){int v=e[k].v,w=e[k].w;if( d[u]+w < d[v] ){d[v]=d[u]+w;if(!vis[v]){if(spfa_dfs(v))return 1;}elsereturn 1;}}vis[u]=0;return 0;
}

總結

以上是生活随笔為你收集整理的spfa(还不懂--）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。