图的最短路径问题 详细分解版
1.图的最短路径问题分类
2.单源最短路问题
2.1边权值都是正数情况
2.1.1 朴素Dijstra算法
算法思想：每次从未被确定最短距离的结点中找出距离起点最小值的结点，加入集合s中，并用该结点更新其他未被确定最短路径值得结点路径。直到最终全部节点的最短路径值都计算出，此时集合s为所有结点集合。
#include<bits/stdc++.h> using namespace std; const int N = 510; int g[N][N];//稠密图，邻接矩阵存储 int st[N];//是否被访问过，即是否在s集合中 int dist[N];//记录每个点到起点的距离 int n,m; //返回编号为n的结点到1号结点的最短路径 int dijstra(){ memset(dist,0x3f,sizeof dist);//将距离初始化为无穷大 dist[1]=0;//1号结点距离初始化为0 for(int i=0;i<n;i++){//n轮循环，每次找出一个结点，加入s集合，并用其更新其他节点dist数组。必须有n轮循环，因为要更新dist数组 int t=-1; for(int j=1;j<=n;j++){//循环找出当前距离起始的1号结点最近，且未加入s的结点 if(!st[j]&&(t==-1||dist[j]<dist[t])){ t=j; } } st[t]=true;//将该结点加入s数组 for(int j=1;j<=n;j++){//循环更新其他节点距离 if(!st[j]){ dist[j]=min(dist[j],dist[t]+g[t][j]); } } } if(dist[n]==0x3f3f3f3f) return -1;//如果dist[n]未被更新，说明其不可达 return dist[n]; } int main(){ memset(g,0x3f,sizeof g);//初始化结点间的距离为无穷大 cin>>n>>m;//输入数据包含n个结点，m条边 int a,b,c; while(m--){ cin>>a>>b>>c;//输入m条边，输入数据存在自环和重边，取最小值即可 g[a][b]=min(g[a][b],c); } cout<<dijstra()<<endl; return 0; } 算法分析：算法包含两轮循环，时间复杂度为(O(n^2))
2.1.2 堆优化的Dijstra算法
优化思想：朴素Dijstra算法每次都要找出当前距离起点最近的结点，加入集合s中。我们可以使用堆来维护结点距离起点的距离，省去一重循环。
//稀疏图的dijstra #include<bits/stdc++.h> using namespace std; const int N = 1.5e5+10; int e[N],ne[N],w[N],h[N],idx;//稀疏图，采用邻接表存储 int n,m;//n个结点，m条边 int dist[N];//距离数组 bool st[N];//是否访问过，即s集合标记 typedef pair<int, int> PII;//使用堆自动排序，pair的first为距离，second为编号 void add(int a,int b,int c){//添加结点a->b的边，权值为c e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int dijstra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; priority_queue<PII,vector<PII>,greater<PII>> q;//声明小根堆 q.push({0,1});//1号结点加入队列 while(!q.empty()){ PII t=q.top(); q.pop(); int distance=t.first,x=t.second; if(st[x]) continue;//距离已经确定，跳过 st[x]=true; for(int i=h[x];i!=-1;i=ne[i]){ int j=e[i]; if(dist[x]+w[i]<dist[j]){ dist[j]=dist[x]+w[i]; q.push({dist[j],j}); } } } if(dist[n]==0x3f3f3f3f) return -1; return dist[n]; } int main(){ cin>>n>>m; int a,b,c; memset(h,-1,sizeof h); while(m--){ cin>>a>>b>>c; add(a,b,c); } cout<<dijstra()<<endl; return 0; } 算法分析：
时间复杂度：每次找到最小距离的点沿着边更新其他的点，若dist[j] > distance + w[i]，表示可以更新dist[j]，更新后再把j点和对应的距离放入小根堆中。由于点的个数是n，边的个数是m，在极限情况下（稠密图(m=frac{n*n(n-1)}{2})）最多可以更新m回，每一回最多可以更新(n^2)个点（严格上是n - 1个点），有m回，因此最多可以把(n^2)个点放入到小根堆中，因此每一次更新小根堆排序的情况是(O(log(n^2)))，一共最多m次更新，因此总的时间复杂度上限是(O(mlog((n^2)))=O(2mlogn)=O(mlogn))
疑问：为什么会存在距离已经确定了点在堆中？
因为可能上次新加入集合s的元素更新了a的距离值，但是距离值很大，直到a的距离值确定了才pop出来。
2.2边权值存在负数的情况
2.2.1 Bellman-ford算法
算法思想：如果图中存在n个点，那么经过n-1次循环，每轮循环时把每条边都进行松弛操作，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
松弛操作：
for n次 for 所有边 a,b,w (松弛操作) dist[b] = min(dist[b],back[a] + w) 注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点。
在下面代码中，是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可。
bellman - ford算法擅长解决有边数限制的最短路问题。
//本代码是解决有边数限制的最短路径问题的代码 #include<bits/stdc++.h> using namespace std; const int N = 10010; int n,m,k; int dist[510],backup[510]; struct{ int a,b,w; }edges[N];//a->b有一条边，权重为w int bellman_ford(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<k;i++){//最多k条边，总共最对经过k条边 memcpy(backup,dist,sizeof dist); for(int j=0;j<m;j++){//对所有的m条边执行松弛操作 int a=edges[j].a,b=edges[j].b,w=edges[j].w; if(backup[a]+w<dist[b]){ dist[b]=backup[a]+w; } } } if(dist[n]>0x3f3f3f3f/2) return -0x3f3f3f3f; else return dist[n]; } int main(){ cin>>n>>m>>k; int a,b,w; for(int i=0;i<m;i++){ cin>>a>>b>>w; edges[i]={a,b,w}; } int ans=bellman_ford(); if(ans==-0x3f3f3f3f){ cout<<"impossible"<<endl; }else{ cout<<ans<<endl; } return 0; } 算法分析：
时间复杂度：(O(nm)),其中n为点数，m为边数
2.2.2 SPFA算法
算法思想：优化了Bellman-ford算法。在Bellman-ford算法中，dist[b] = min(dist[b],back[a] + w),如果a的距离没有更新，那么我的循环其实做了很多没用的操作。所以我们希望当a的距离更新时 ，再去用a更新其他结点的距离值。算法思想类似于Dijstra算法。
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int e[N],w[N],h[N],ne[N],idx; int n,m; int st[N];//记录结点是否在队列中，即是否发生更新 int dist[N]; void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int spfa(){ memset(dist,0x3f,sizeof dist); dist[1]=0; queue<int> q; q.push(1); while(!q.empty()){ int t=q.front(); q.pop(); st[t]=false; 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]=true; } } } } if(dist[n]==0x3f3f3f3f) return -0x3f3f3f3f; return dist[n]; } int main(){ memset(h,-1,sizeof h); cin>>n>>m; int a,b,c; while(m--){ cin>>a>>b>>c; add(a,b,c); } int ans=spfa(); if(ans==-0x3f3f3f3f) cout<<"impossible"<<endl; else cout<<ans<<endl; return 0; } 算法分析：
Bellman_ford算法里最后return -1的判断条件写的是dist[n]>0x3f3f3f3f/2;而spfa算法写的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。
Bellman_ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；但是SPFA算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用SPFA否则会死循环。
由于SPFA算法是由Bellman_ford算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 (O(nm)) ，假如题目时间允许可以直接用SPFA算法去解Dijkstra算法的题目。
求负环一般使用SPFA算法，方法是用一个cnt数组记录每个点到源点的边数，一个点被更新一次就+1，一旦有点的边数达到了n那就证明存在了负环。
3.多源汇最短路径问题
Floyd算法
算法思想：三重循环，动态规划思想。(dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]))
#include<bits/stdc++.h> using namespace std; const int N = 510,INF=1e9; int g[N][N];//g[i][j]记录i->j的最短路径 int n,m,Q; void floyd(){ 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]); } } } } int main(){ cin>>n>>m>>Q; for(int i=1;i<=n;i++){//初始化数组 for(int j=1;j<=n;j++){ if(i==j) g[i][j]=0; else g[i][j]=INF; } } while(m--){//输入m条边 int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); } floyd(); while(Q--){//Q次查询 int a,b; cin>>a>>b; if(g[a][b]>INF/2) cout<<"impossible"<<endl; else cout<<g[a][b]<<endl; } return 0; } 算法分析：三重循环，floyd算法时间复杂度为(O(n))
