最短路分为单源最短路和多源汇最短路；
1单源最短路根据边长的正负分为两类（n表示点，m表示边）
（1）边长为正
dijkstra算法
朴素版（o(n^2)）
堆优化版（0（mlogn))
当稠密图（m>=n^2)时朴素版的时间更优，稀疏图则用堆优化版更优；
（2）边权有负
bellman_ford算法 0（nm）
由于SPFA算法是bellman_ford的优化，bellman_ford常用于求有边数限制的最短路，如在不经过超过k条边时的最短路，注意这时的不存在最短路的临界条件是dist[n]>0x3f3f3f3f,因为可能存在，dist[t]=0x3f3f3f3f,但存在t到n的边可能松弛dist[n]；
SPFA O(m),最坏O(nm)
还可用来求负环，也可以用来求正权最短路
2.多源汇最短路
folyd算法 0（n^3) 适合稠密图
dijkstra算法朴素版
#include<iostream> #include<cstring> using namespace std; int g[510][510]; int n,m; int vis[510],dist[510]; int dijkstra() { memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++) { if(!vis[j]&&(t==-1||dist[t]>dist[j])) t=j; } vis[t]=1; for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]); } if(dist[n]==0x3f3f3f3f)return -1; return dist[n]; } int main() { memset(g,0x3f,sizeof g); cin>>n>>m; while(m--) { int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); //g[b][a]=min(g[b][a],c); } cout<<dijkstra()<<endl; return 0; }
堆优化版
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef pair<int,int> PII; const int N=100010; int h[N],e[N],ne[N],idx,w[N]; int dist[N]; bool st[N]; int n,m; void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int dijktra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; priority_queue<PII,vector<PII>,greater<PII>>heap; heap.push({0,1}); while(heap.size()){ auto t=heap.top(); heap.pop(); int ver=t.second,distance=t.first; if(distance>dist[ver])continue; for(int i=h[ver];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j]>distance+w[i]) { dist[j]=distance+w[i]; heap.push({dist[j],j}); } } } if(dist[n]==0x3f3f3f3f)return -1; return dist[n]; } int main(){ memset(h,-1,sizeof h); cin>>n>>m; while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } cout<<dijktra()<<endl; return 0; }
bellman_ford求有边数限制
#include<iostream> #include<queue> #include<cstring> using namespace std; int n,m,k; int dist[510],bakcup[510]; struct Edge { int a,b,w; }edge[10010]; int bellmen_ford() { memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<k;i++) { memcpy(bakcup,dist,sizeof dist);//拷贝dist数组到bakcup防止发生串联 for(int j=0;j<m;j++) { int a=edge[j].a,b=edge[j].b,w=edge[j].w; dist[b]=min(dist[b],bakcup[a]+w);//对每一条边a->b进行松弛 } } if(dist[n]>0x3f3f3f3f/2)return -1; return dist[n]; } int main() { cin>>n>>m>>k; for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; edge[i]={a,b,w}; } int t=bellmen_ford(); if(t==-1)printf("impossible "); else printf("%d ",dist[n]); return 0; }
SPEA求最短路（前提是不存在负环）
#include<iostream> #include<cstring> #include<queue> using namespace std; int h[100010],ne[100010],e[100010],w[100010],idx; int dist[100010],st[100010];int n,m; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } int spea() { memset(dist,0x3f,sizeof dist); dist[1]=0; queue<int>q; st[1]=1;q.push(1); while(q.size()) { int t=q.front(); q.pop(); st[t]=0;//t出队 for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q.push(j); st[j]=1; } } } } if(dist[n]==0x3f3f3f3f)return -1;//完全做完后一定为最小值 return dist[n]; } int main() { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int a,b,w;cin>>a>>b>>w; add(a,b,w); } int t=spea(); if(t==-1)printf("impossible "); else printf("%d ",t); return 0; }
SPFA判断负环
#include<iostream> #include<cstring> #include<queue> using namespace std; int h[100010],ne[100010],e[100010],w[100010],idx; int dist[100010],st[100010];int n,m,cnt[100010]; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } int spea() { memset(dist,0x3f,sizeof dist); dist[1]=0; queue<int>q; for(int i=1;i<=n;i++) st[i]=1,q.push(i);//负环不仅在1开始的路径上 while(q.size()) { int t=q.front(); q.pop(); st[t]=0;//t出队 for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; cnt[j]=cnt[t]+1;//该路径多了一条边 if(cnt[j]>=n)return 1;//抽屉原理，经过n条边，即经过n+1个点，必有两个相同的点 if(!st[j]) { q.push(j); st[j]=1; } } } } return 0; } int main() { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int a,b,w;cin>>a>>b>>w; add(a,b,w); } int t=spea(); if(t)printf("Yes "); else printf("No"); return 0; }
folyd
#include<iostream> #include<cstring> using namespace std; int g[510][510]; int main() { memset(g,0x3f,sizeof g); int n,m,k;cin>>n>>m>>k; for(int i=1;i<=n;i++)g[i][i]=0; while(m--) { int a,b,c; cin>>a>>b>>c; g[a][b]=min(c,g[a][b]); } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); while(k--) { int a,b; cin>>a>>b; if(g[a][b]>0x3f3f3f3f/2)printf("impossible "); else printf("%d ",g[a][b]); } return 0; }