Dijkstra：適用于權值為非負的圖的單源最短路徑，用斐波那契堆的復雜度O(E+VlgV)
BellmanFord：適用于權值有負值的圖的單源最短路徑，并且能夠檢測負圈，復雜度O(VE)
SPFA：適用于權值有負值，且沒有負圈的圖的單源最短路徑，論文中的復雜度O(kE)，k為每個節點進入Queue的次數，且k一般<=2，但此處的復雜度證明是有問題的，其實SPFA的最壞情況應該是O(VE).
Floyd：每對節點之間的最短路徑。

先給出結論：
(1)當權值為非負時，用Dijkstra。
(2)當權值有負值，且沒有負圈，則用SPFA，SPFA能檢測負圈，但是不能輸出負圈。
(3)當權值有負值，而且可能存在負圈，則用BellmanFord，能夠檢測并輸出負圈。
(4)SPFA檢測負環：當存在一個點入隊大于等于V次，則有負環，后面有證明。

模板就是這些模板，但是這種題通常不會在比賽中單方面考察最短路算法，更多是最短路與圖，與環，負環，負權值，連通塊等，一同考察，要學會改版子，考慮有向圖有環圖，有向無環圖，沒有直接的最短路算法可以解決時，要考慮數據量，然后選擇一種最短路，找到合適的改造方法，構造出可以使用該算法的圖，進而使用最短路算法，而構造的方法千奇百怪，這絕不是大量練習就能遇到的，而是在練習中尋找一種思考方式，進而能夠對陌生題目進行分析，得出合適的解決方案。

學好最短路原理的方法，不是看大牛的講解，而是自己舉一組樣例，按照程序的思路去跑一遍，按照他的想法，就能理解算法的設計界原理，比看要記得牢。

BFS相關：https://blog.csdn.net/weixin_43627118/article/details/100088087

DFS相關：https://blog.csdn.net/weixin_43627118/article/details/100107848

floyd技巧：https://blog.csdn.net/weixin_43627118/article/details/100129268

超級源點&匯點：https://blog.csdn.net/weixin_43627118/article/details/100134565

鏈式前向星（邊集數組）：https://mp.csdn.net/postedit/99612887

Floyd 算法戳這里：https://blog.csdn.net/weixin_43627118/article/details/90387061

//最基礎的Dijkstra，用于理解算法本質原理，適用的類型于隊列優化的一樣，但是時間復雜度太高，所以，用的比較少。 #include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0) #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int maxn=1e3+10; const double esp=1e-9; //-------------------------------------------------------//int n,m; //n個節點，m條邊 int dis[maxn][maxn]; bool vis[maxn]; int d[maxn]; inline void dijstra(); int main() {mem(dis,0x3f);mem(vis,0);mem(d,0x3f);for(int i=1; i<=n; i++)dis[i][i]=0;cini(m),cini(n);//輸入邊數//點數for(int i=0; i<m; i++){int x,y,z;cini(x),cini(y),cini(z);dis[x][y]=min(dis[x][y],z);dis[y][x]=min(dis[y][x],z);//cout<<dis[x][y]<<endl;}dijstra();cout<<d[n]<<endl; } inline void dijstra() {d[1]=0;for(int i=1; i<=n; i++){int x=0;for(int j=1; j<=n; j++)if(!vis[j]&&(d[j]<d[x]||x==0))x=j;vis[x]=1;for(int j=1;j<=n;j++)d[j]=min(d[j],d[x]+dis[x][j]);} } #include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0) #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define INF 0x3f3f3f3f #define maxn 100010 #define esp 1e-9 #define mp(a,b) make_pair(a,b) using namespace std; typedef long long ll; //-----------------------*******----------------------------//int next[maxn*10],ege[maxn*10],head[maxn],ver[maxn*10],d[maxn]; bool vis[maxn]; int tot=0; void add(int x,int y,int z) //аз╫с╠М {ege[++tot]=z;next[tot]=head[x];head[x]=tot;ver[tot]=y;//有向圖建一條邊，無向圖反向建邊// ege[++tot]=z;// next[tot]=head[y];// head[y]=tot;// ver[tot]=x; } int n,m; inline void dijkstra(); int main() {mem(vis,0);mem(d,0x3f);cini(m);cini(n);for(int i=0; i<m; i++){int x,y,z;cini(x),cini(y),cini(z);add(x,y,z);}dijkstra();cout<<d[n]<<endl; } inline void dijkstra() {d[1]=0;priority_queue<pair<int,int> >qu;while(qu.size())qu.pop();qu.push(mp(0,1));while(qu.size()){//cout<<qu.size()<<endl;int x=qu.top().second;qu.pop();if(vis[x])continue;vis[x]=1;for(int i=head[x]; i; i=next[i]){int y=ver[i],z=ege[i];if(d[y]>=d[x]+z){d[y]=d[x]+z;qu.push(mp(-d[y],y));}}} } //Ford 算法有一點DP的思想，同樣的松弛操作，但是時間復雜度略高 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0) #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define INF 0x3f3f3f3f #define maxn 100010 #define esp 1e-9 #define mp(a,b) make_pair(a,b) using namespace std; typedef long long ll; //-----------------------*******----------------------------// int n,m; int ege[maxn*10],head[maxn],later[maxn*10],dis[maxn]; bool vis[maxn]; inline bool ford() {mem(vis,0);mem(dis,0x3f);vis[1]=1;dis[1]=0;for(int i=1; i<n; i++) //n-1′??-?·{int check=1;for(int j=1; j<=m; j++){if(vis[head[j]]||vis[later[j]]){if(dis[head[j]]+ege[j]<dis[later[j]]){dis[later[j]] =dis[head[j]]+ege[j];vis[later[j]]=1;check=0;}if(dis[later[j]]+ege[j]<dis[head[j]])//有向圖，不用反向松弛{dis[head[j]] =dis[later[j]]+ege[j];vis[head[j]]=1;check=0;}}}if(check)break;}for(int i=1; i<m; i++)if(dis[head[i]]+ege[i]<dis[later[i]])return 1;return 0; } int main() {cini(m),cini(n);for(int i=1; i<=m; i++){cini(head[i]);cini(later[i]);cini(ege[i]);}ford();cout<<dis[n]; } SPFA，是隊列優化的ford算法 #include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0) #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define INF 0x3f3f3f3f #define maxn 100010 #define esp 1e-9 #define mp(a,b) make_pair(a,b) using namespace std; typedef long long ll; //-----------------------*******----------------------------// int next[maxn*10],ege[maxn*10],head[maxn],ver[maxn*10],d[maxn]; bool vis[maxn]; int tot=0,n,m; void add(int x,int y,int z) {next[++tot]=head[x];ege[tot]=z;ver[tot]=y;head[x]=tot;next[++tot]=head[y];ege[tot]=z;ver[tot]=x;head[y]=tot; } void spfa(int w) {mem(d,0x3f);mem(vis,0);vis[w]=1;d[w]=0;queue<int> q;while(q.size()) q.pop();q.push(w);while(q.size()){int x=q.front();q.pop();vis[x]=0;for(int i=head[x];i;i=next[i]){int y=ver[i],z=ege[i];if(d[y]>d[x]+z){d[y]=d[x]+z;if(!vis[y]) q.push(y),vis[y]=1;}}} } int main() {cini(m);cini(n);for(int i=0; i<m; i++){int x,y,z;cini(x),cini(y),cini(z);add(x,y,z);}int w;cin>>w;spfa(w);for(int i=1;i<=n;i++)cout<<d[i]<<endl; }

?

總結

以上是生活随笔為你收集整理的疯子的算法总结(八) 最短路算法+模板的全部內容，希望文章能夠幫你解決所遇到的問題。

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