引入1：單源最短路

問：求帶權(quán)有向圖上一個(gè)源點(diǎn)到其他點(diǎn)的最短路徑距離

如果沒有非負(fù)邊權(quán)，我們自然可以想到dij。但是如果有負(fù)邊權(quán)呢？這時(shí)候就要用SPFA算法求解。

原理&講解

用dis數(shù)組記錄源點(diǎn)到有向圖上任意一點(diǎn)距離，其中源點(diǎn)到自身距離為0，到其他點(diǎn)距離為INF。將源點(diǎn)入隊(duì)，并重復(fù)以下步驟：

• 隊(duì)首x出隊(duì)
• 遍歷所有以隊(duì)首為起點(diǎn)的有向邊(x,i)，若dis[x]+w(x,i)<dis[i]，則更新dis[i]
• 如果點(diǎn)i不在隊(duì)列中，則i入隊(duì)
• 若隊(duì)列為空，跳出循環(huán)；否則執(zhí)行1

實(shí)際上我們可以將其理解為bfs

如果圖是隨機(jī)生成的，時(shí)間復(fù)雜度為 O(KM) （K可以認(rèn)為是個(gè)常數(shù)，m為邊數(shù)，n為點(diǎn)數(shù)）

但是實(shí)際上SPFA的算法復(fù)雜度是 O(NM) ，可以構(gòu)造出卡SPFA的數(shù)據(jù)，讓SPFA超時(shí)。

在NOI 2018的第一天第一題中，出題人卡了SPFA算法，導(dǎo)致100分變成60分，所以在沒有負(fù)環(huán)、單純求最短路徑，不建議使用SPFA算法，而是用Dijkstra算法。

在初一我們學(xué)到一條三角形中的性質(zhì)，即同一三角形內(nèi)兩邊之和大于第三邊。而最短路中如u->v的最短路它是小于等于其它任意路徑的，這使我們?nèi)菀讁y到三角形。也就是說，我們實(shí)際上每次都是在判斷這條路徑符不符合三角形不等式，若不符合，我們就將原先的路徑松弛為現(xiàn)在的路徑，使得現(xiàn)在的路徑滿足三角形不等式。但是為什么松弛后要將終點(diǎn)入隊(duì)呢？SPFA的過程是BFS，它是不停擴(kuò)展節(jié)點(diǎn)的。而當(dāng)我們更新了這一條路徑，那么可能會(huì)出現(xiàn)基于這一條路徑的新路，我們需要判斷原路與新路是否滿足三角形不等式。

模擬&代碼

我們可以手推這張圖模擬一下~

我們以1為源點(diǎn)，初始化：dis[源點(diǎn)]=0，其他為正無窮，并將源點(diǎn)入隊(duì)。

隊(duì)首1出隊(duì)，并枚舉它的出邊1->2,1->3。由dis[1]+w(1,2)=1<dis[2]=INF,dis[1]+w(1,3)=6<dis[3]=INF得dis[2]=dis[1]+w(1,2)=1,dis[3]=dis[1]+w(1,3)=6，并將2，3入隊(duì)。

隊(duì)首2出隊(duì)，枚舉它的出邊2->3,2->4,2->5。都不滿足三角形不等式，所以松弛它們。并將3，4，5入隊(duì)，但由于3已在隊(duì)內(nèi)，所以不管。

隊(duì)首3出隊(duì)，沒有能松弛的邊，直接略過。

此時(shí)隊(duì)內(nèi)剩下4，5，由于這兩點(diǎn)沒有出邊，所以在此不枚舉。

手繪勿噴

下面是帶注釋代碼：

#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<string> #include<cstdio> #include<cstdlib> #include<queue> #define N 110000 #define INF 0x3f3f3f3f using namespace std;int n,m,a,b,c,vis[N],dis[N];struct node {int d,w; };//定義一個(gè)結(jié)構(gòu)體來存儲(chǔ)每個(gè)入度點(diǎn)以及對(duì)應(yīng)邊的權(quán)值 //比如邊u->v,權(quán)值為w,node結(jié)構(gòu)體存儲(chǔ)的就是v以及w。vector<node>v[N];void spfa(int u);int main() {//對(duì)于N非常大但是M很小的這種稀疏圖來說，用鄰接矩陣N*N是存不下的。鄰接矩陣是將所有的點(diǎn)都存儲(chǔ)下來了，然而//對(duì)于稀疏圖來說，有很多點(diǎn)是沒有用到的，把這些點(diǎn)也存儲(chǔ)下來的話就會(huì)很浪費(fèi)空間。可以用鄰接表來存儲(chǔ)，這里借助vector來實(shí)現(xiàn)鄰接表的操作。//用鄰接表存儲(chǔ)時(shí)候，只存儲(chǔ)有用的點(diǎn)，對(duì)于沒有用的點(diǎn)不存儲(chǔ)，實(shí)現(xiàn)空間的優(yōu)化。cin>>n>>m;for(int i=0; i<=n; i++)v[i].clear();//將vecort數(shù)組清空for(int i=1; i<=m; i++) //用vector存儲(chǔ)鄰接表{node nd;scanf("%d%d%d",&a,&b,&c);nd.d=b,nd.w=c;//將入度的點(diǎn)和權(quán)值賦值給結(jié)構(gòu)體v[a].push_back(nd);//將每一個(gè)從a出發(fā)能直接到達(dá)的點(diǎn)都?jí)旱较聵?biāo)為a的vector數(shù)組中，以后遍歷從a能到達(dá)的點(diǎn)就可以直接遍歷v[a]// nd.d=a,nd.w=c;//無向圖的雙向存邊// v[b].push_back(nd);}spfa(1);if(dis[n]!=INF)printf("%d\n",dis[n]);elseprintf("impossible");return 0; } void spfa(int u){memset(vis,1,sizeof(vis));memset(dis,0x3f,sizeof(dis));dis[u]=0;queue<int> q;q.push(u);vis[u]=false;while (!q.empty()) {int x=q.front();q.pop();vis[x]=true;vector<node> s=v[x];for (int i = 0; i < s.size(); ++i) {int v=s[i].d;if(dis[x]+s[i].w<dis[v]){dis[v]=dis[x]+s[i].w;if(vis[v]){q.push(v);vis[v]=false;}}}} }

引入2：判正(負(fù))環(huán)

spfa算法還可以在有向圖內(nèi)判正環(huán)負(fù)環(huán)，我們可以使用DFS/BFS版SPFA。注意，判負(fù)環(huán)跑最短路，判正環(huán)跑最長(zhǎng)路。

#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<string> #include<cstdio> #include<cstdlib> #include<queue> #define N 110000 #define INF 0x3f3f3f3f using namespace std;int n,m,a,b,c,instack[N],dis[N],flag;struct node {int d,w; };//定義一個(gè)結(jié)構(gòu)體來存儲(chǔ)每個(gè)入度點(diǎn)以及對(duì)應(yīng)邊的權(quán)值 //比如邊u->v,權(quán)值為w,node結(jié)構(gòu)體存儲(chǔ)的就是v以及w。vector<node>v[N];void spfa(int u);int main() {//對(duì)于N非常大但是M很小的這種稀疏圖來說，用鄰接矩陣N*N是存不下的。鄰接矩陣是將所有的點(diǎn)都存儲(chǔ)下來了，然而//對(duì)于稀疏圖來說，有很多點(diǎn)是沒有用到的，把這些點(diǎn)也存儲(chǔ)下來的話就會(huì)很浪費(fèi)空間。可以用鄰接表來存儲(chǔ)，這里借助vector來實(shí)現(xiàn)鄰接表的操作。//用鄰接表存儲(chǔ)時(shí)候，只存儲(chǔ)有用的點(diǎn)，對(duì)于沒有用的點(diǎn)不存儲(chǔ)，實(shí)現(xiàn)空間的優(yōu)化。cin>>n>>m;for(int i=0; i<=n; i++)v[i].clear();//將vecort數(shù)組清空for(int i=1; i<=m; i++) //用vector存儲(chǔ)鄰接表{node nd;scanf("%d%d%d",&a,&b,&c);nd.d=b,nd.w=c;//將入度的點(diǎn)和權(quán)值賦值給結(jié)構(gòu)體v[a].push_back(nd);//將每一個(gè)從a出發(fā)能直接到達(dá)的點(diǎn)都?jí)旱较聵?biāo)為a的vector數(shù)組中，以后遍歷從a能到達(dá)的點(diǎn)就可以直接遍歷v[a]// nd.d=a,nd.w=c;//無向圖的雙向存邊// v[b].push_back(nd);}memset(instack,0,sizeof(instack));memset(dis,0,sizeof(dis));flag=0;for(int i=1;i<=n;i++){spfa(i);if(flag)break;}if(flag)printf("Yes");else printf("No");return 0; } void spfa(int u){if(instack[u]){flag=1;return;}instack[u]=true;vector<node> s=v[u];for (int i = 0; i < s.size(); ++i) {if(dis[u]+s[i].w<dis[s[i].d]){dis[s[i].d]=dis[u]+s[i].w;spfa(s[i].d);if(flag)return;}}instack[u]=false; }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/clarencezzh/p/10382939.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的最短路径之spfa的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。