適用范圍：給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復雜度又過高，SPFA算法便派上用場了。 我們約定有向加權圖G不存在負權回路，即最短路徑一定存在。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權回路，但這不是我們討論的重點。

算法思想：我們用數組d記錄每個結點的最短路徑估計值，用鄰接表來存儲圖G。我們采取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，并且用u點當前的最短路徑估計值對離開u點所指向的結點v進行松弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止

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

實現方法：

　　建立一個隊列，初始時隊列里只有起始點，再建立一個表格記錄起始點到所有點的最短路徑（該表格的初始值要賦為極大值，該點到他本身的路徑賦為0）。然后執行松弛操作，用隊列里有的點作為起始點去刷新到所有點的最短路，如果刷新成功且被刷新點不在隊列中則把該點加入到隊列最后。重復執行直到隊列為空。

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

首先建立起始點a到其余各點的
最短路徑表格

首先源點a入隊，當隊列非空時：
　１、隊首元素（a）出隊，對以a為起始點的所有邊的終點依次進行松弛操作（此處有b,c,d三個點），此時路徑表格狀態為：

?

在松弛時三個點的最短路徑估值變小了，而這些點隊列中都沒有出現，這些點
需要入隊，此時，隊列中新入隊了三個結點b,c,d

隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處只有e點），此時路徑表格狀態為：

?

在最短路徑表中，e的最短路徑估值也變小了，e在隊列中不存在，因此e也要
入隊，此時隊列中的元素為c，d，e

隊首元素c點出隊，對以c為起始點的所有邊的終點依次進行松弛操作（此處有e,f兩個點），此時路徑表格狀態為：

在最短路徑表中，e，f的最短路徑估值變小了，e在隊列中存在，f不存在。因此
e不用入隊了，f要入隊，此時隊列中的元素為d，e，f

?隊首元素d點出隊，對以d為起始點的所有邊的終點依次進行松弛操作（此處只有g這個點），此時路徑表格狀態為：

在最短路徑表中，g的最短路徑估值沒有變小（松弛不成功），沒有新結點入隊，隊列中元素為f，g

隊首元素f點出隊，對以f為起始點的所有邊的終點依次進行松弛操作（此處有d，e，g三個點），此時路徑表格狀態為：

在最短路徑表中，e，g的最短路徑估值又變小，隊列中無e點，e入隊，隊列中存在g這個點，g不用入隊，此時隊列中元素為g，e

隊首元素g點出隊，對以g為起始點的所有邊的終點依次進行松弛操作（此處只有b點），此時路徑表格狀態為：

在最短路徑表中，b的最短路徑估值又變小，隊列中無b點，b入隊，此時隊列中元素為e，b
隊首元素e點出隊，對以e為起始點的所有邊的終點依次進行松弛操作（此處只有g這個點），此時路徑表格狀態為：

在最短路徑表中，g的最短路徑估值沒變化（松弛不成功），此時隊列中元素為b

隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處只有e這個點），此時路徑表格狀態為：

在最短路徑表中，e的最短路徑估值沒變化（松弛不成功），此時隊列為空了

最終a到g的最短路徑為１４

?(⊙v⊙)嗯！ 代碼：

1 #include 2 #include 3 #include 4 using namespace std; 5 6 const int MAXN=1001; 7 const int INF=999999; 8 9 int map[MAXN][MAXN];//記錄權值 10 int path[MAXN];//記錄路徑 11 int dis[MAXN];//記錄最短值 12 int team[MAXN];//隊列 13 bool visit[MAXN];//是否在隊列中 14 int n,m,u,v,len,a,e; 15 16 void sc(int u)//求最短路徑 17 { 18 int head=0,tail=1,p; 19 team[head]=u;//隊列的第一個為起點 20 path[u]=u;//路徑為起點 21 visit[u]=true;//標記為已在隊列中 22 dis[u]=0;//起點的權值為0 23 while(headdis[p]+map[p][i])//松弛 24 { 25 dis[i]=dis[p]+map[p][i]; 26 path[i]=p; 27 if(!visit[i])//如果不在隊列中，重新入隊 28 { 29 team[tail++]=i; 30 visit[i]=true;//標記已為在隊列中 31 } 32 } 33 } 34 visit[p]=false;//將p標記為沒在隊列中 35 head++;//head后移，head所指向的元素依次出隊 36 } 37 cout<=1;i--)//輸出路徑 38 { 39 if(i!=1)//避免最后一個路徑帶有--> 40 cout<"; 41 else 42 cout<>n>>m; 43 for(int i=1;i<=n;i++)//初始化 44 for(int j=1;j<=n;j++) 45 map[i][j]=INF; 46 for(int i=1;i<=m;i++){ 47 cin>>u>>v>>len; 48 map[u][v]=len; 49 } 50 for(int i=1;i<=n;i++) 51 dis[i]=INF; 52 memset(visit,false,sizeof(visit)); 53 memset(team,0,sizeof(team)); 54 cin>>a>>e;//輸入查找的起點和終點 55 sc(a); 56 out(a,e); 57 return 0; 58 }

? ?ps：可以用鄰接表實現，效率更高，鄰接矩陣容易炸空間。。。

?

自己選的路，跪著也要走完！！

?

轉載于:https://www.cnblogs.com/wsdestdq/p/6697605.html

總結

以上是生活随笔為你收集整理的SPFA 算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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