六、Dijkstra算法
源点即起点，汇点即终点。
n表示点数，m表示边数
稠密图：m和n2一个级别
稀疏图：m和n一个级别
核心模板
稠密图用邻接矩阵存储，稀疏图用邻接表存储。
朴素dijkstra算法
时间复杂度是O(n2+m)，n表示点数，m表示边数
int g[N][N]; //存储每条边 int dist[N][N]; //存储1号点到每个点的最短距离 bool st[N]; //存储每个点的最短路是否已经确定 //求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<n-1;i++){ int t=-1; //在还未确定最短路的点中，寻找距离最小的点 for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } //用t更新其他点的距离 for(int j=1;j<=n;j++){ dist[j]=min(dist[j],dist[t]+g[t][j]); } st[t]=true; } if(dist[n]==0x3f3f3f3f) return -1; return dist[n]; }
下图来自AcWing官网，作者们如图，侵权删。
堆优化版dijkstra
手写堆可以保证堆中元素个数一定，而优先队列不可以修改任意一个元素，只能继续插入新的点，有冗余。
下图来自AcWing官网，作者们如图，侵权删。
时间复杂度是O(mlogn)，n表示点数，m表示边数。
typedef pair<int,int> PII; int n; //点的数量 int h[N],w[M],e[M],ne[M],idx; //领接表存储所有边 int dist[N]; //存储所有点到1号点的距离 bool st[N]; //存储每个点的最短距离是否已确定 //求1号点到n号点的最短距离，如果不存在，则返回-1 int dijkstra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push({0,1}); //first存储距离，second存储节点编号 while(heap.size()){ auto t=heap.top(); heap.pop(); int ver=t.second,distance=t.first; //distance等同于dist[ver] if(st[ver]) continue; st[ver]=true; 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}); //注意与spfa区分，此时只要更新最短路就入堆 } } } if(dist[n]==0x3f3f3f3f) return -1; return dist[n]; }
题目一
题目链接：849. Dijkstra求最短路 I
6.1题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1 。
输入格式
第一行包含整数 n 和 m 。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1 。
数据范围
1≤n≤500,1≤m≤105,图中涉及边长均不超过10000。
输入样例：
3 3 1 2 2 2 3 1 1 3 4
6.2思路分析
套用模板即可，注意细节
6.3代码实现
#include <iostream> #include <cstring> using namespace std; const int N=510; int n,m; int g[N][N]; //稠密图用领接矩阵存储，存储两个点之间的距离 int dist[N]; //存储从1号点走到每个点的当前最短距离 bool st[N]; //存储每个点的最短路是否确定 int dijkstra(){ memset(dist,0x3f,sizeof dist); //初始化从1号点走到每个点的距离为正无穷 dist[1]=0; //1号点走到自己的最短距离为0 for(int i=0;i<n;i++){ int t=-1; //t在还未确定最短路的点中寻找距离最短的点 for(int j=1;j<=n;j++){ //在st[]=false的点中找dist[]最小的点 //如果当前点没有确定最短路而且t没有更新过或者当前点没有确定最短路而且t已经更新过，但是j离1号点距离更短，则更新t if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } st[t]=true; //t已确定最短路 //更新最短路，看是否存在从t走到j再走到终点的距离比j直接走到终点距离小，若存在则更新 for(int j=1;j<=n;j++){ dist[j]=min(dist[j],dist[t]+g[t][j]); } } //如果最短路没有被更新过，说明走不到终点返回-1，否则返回最短路 if(dist[n]==0x3f3f3f3f) return -1; return dist[n]; } int main(){ cin>>n>>m; //初始化邻接矩阵 memset(g,0x3f,sizeof g); while(m--){ int a,b,c; cin>>a>>b>>c; //因为存在重边和自环，所以两点间距离取最短的即可 g[a][b]=min(g[a][b],c); } int t=dijkstra(); cout<<t; return 0; }
题目二
题目链接：850. Dijkstra求最短路 II
6.4题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1 。
输入格式
第一行包含整数 n 和 m 。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105,图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。
输入样例：
3 3 1 2 2 2 3 1 1 3 4
6.5思路分析
利用堆优化dijkstra算法，套用模板即可，注意细节。
6.6代码实现
#include <iostream> #include <cstring> #include <queue> #include <utility> using namespace std; typedef pair<int,int> PII; //两个值分别存储每个点到1号点最短距离和点编号 const int N=150010; int n,m; int h[N],w[N],e[N],ne[N],idx; //邻接表存储每条边,w[]代表每条边的权重 int dist[N]; //存储1号点到n号点的最短距离 bool st[N]; //存储每个点的最短距离是否已经确定 //邻接表加边 void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int dijkstra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; //1号点到1号点（自己）的距离为0 priority_queue<PII,vector<PII>,greater<PII>> heap; //建立小根堆 heap.push({0,1}); //将起点放入堆中 while(heap.size()){ auto t=heap.top(); //t取出当前距离最小的点（即堆顶元素） heap.pop(); int ver=t.second,distance=t.first; if(st[ver]) continue; //如果堆顶元素已被访问过，直接跳过后续，找下一个距离最小的点 st[ver]=true; //否则，标记该点已被访问过 for(int i=h[ver];i!=-1;i=ne[i]){ //遍历这个点的所有邻边 int j=e[i]; if(dist[j]>distance+w[i]){ //如果从1号点到ver点再到j点的距离比从1号点直接到j点的距离小，则更新1号点到j的最短距离为前者 dist[j]=distance+w[i]; heap.push({dist[j],j}); //把更新后的的距离和该点编号，入堆 } } } if(dist[n]==0x3f3f3f3f) return -1; //如果无法从1号点到达n号点返回-1 return dist[n]; //否则返回从1号点到n号点的距最短离 } int main(){ cin>>n>>m; memset(h,-1,sizeof h); while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } int t=dijkstra(); cout<<t; return 0; }
七、Bellman-Ford算法
存在最短路则一定不存在负权回路，如果存在负权回路则最短路可能是负无穷。
时间复杂度O(nm)，n表示点数，m表示边数
核心模板
int n,m; //n表示点数，m表示边数 int dist[N]; //dist[x]存储1到x的最短路距离 struct Edge{ //边，a表示出点，b表示入点，w表示边的权重 int a,b,w; }edge[M]; //求1到n的最短路距离，如果无法从1走到n，返回-1 int bellman_ford(){ memset(dist,0x3f,sizeof dist); dist[1]=0; //如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int a=edges[j].a,b=edges[j].b,w=edges[j].w; if(dist[b]>dist[a]+w) dist[b]=dist[a]+w; } } if(dist[n]>0x3f3f3f3f/2) return -1; return dist[n]; }
题目链接：853. 有边数限制的最短路
7.1题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z 。
点的编号为 1∼n。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,1≤m≤10000,1≤x,y≤n，任意边长的绝对值不超过 10000。
输入样例：
3 3 1 1 2 1 2 3 1 1 3 3
输出样例：
7.2思路分析
套用模板即可，注意细节。
7.3代码实现
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N=510,M=10010; int n,m,k; int backup[N]; //存储上一次循环中dist[]数组的值 int dist[N]; //存储1号点到n号点的最短距离 //利用结构体存每条边：a起点，b终点，w权重 struct Edge{ int a,b,w; }edges[M]; int bellman_ford(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<k;i++){ memcpy(backup,dist,sizeof dist); //每次迭代需备份，确保更新只用到上一次的结果 for(int j=0;j<m;j++){ int a=edges[j].a,b=edges[j].b,w=edges[j].w; dist[b]=min(dist[b],backup[a]+w); } } if(dist[n]>0x3f3f3f3f/2) return -3; //不能写成==，如果图中某个点是无法到达，到达该点的最短距离为0x3f3f3f3f，而这个点到最后一个点的最短距离为-1，则会导致dist[n]！=0x3f3f3f3f,但是这个点不能到达n号点 return dist[n]; } int main(){ cin>>n>>m>>k; for(int i=0;i<m;i++){ int a,b,w; cin>>a>>b>>w; edges[i]={a,b,w}; } int t=bellman_ford(); if(t==-3) cout<<"impossible"; else cout<<t; return 0; }
八、spfa算法（队列优化的Bellman-Ford算法）
spfa算法
时间复杂度平均情况下O(m)，最坏情况下O(nm)，n表示点数，m表示边数
核心模板
int n; //总点数 int h[N],w[N],e[N],ne[N],idx; //领接表存储所有边 int dist[N]; //存储每个点到1号点的最短距离 bool st[N]; //存储每个点是否在队列中 //求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 int spfa(){ memset(dist,0x3f,sizeof dist); dist[1]=0; queue<int> q; q.push(1); st[1]=true; while(q.size()){ auto 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]; //注意与dijkstra堆优化区分，此时如果不在队列才入队 if(!st[j]){ //注意该判断语句的位置（在第一个if中） //如果队列中已存在j，则不需要将j重复插入 q.push(j); st[j]=true; } } } } if(dist[n]==0x3f3f3f3f) return -1; return dist[n]; }
0
spfa判断图中是否存在负环
时间复杂度是O(nm)，n表示点数，m表示边数
int n; //总点数 int h[N],w[N],e[N],ne[N],idx; //领接表存储所有边 int dist[N],cnt[N]; //dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数 bool st[N]; //存储每个点是否在队列中 //如果存在负环，则返回true，否则返回false bool spfa(){ //不需要初始化dist数组 //原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理，一定有两个点相同，所以存在环。 queue<int> q; for(int i=1;i<=n;i++){ q.push(i); st[i]=true; } while(q.size()){ auto 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]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; //如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环 if(!st[j]){ q.push(j); st[j]=true; } } } } return false; }
题目一
题目链接：851. spfa求最短路
8.1题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤105,图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 1 2 5 2 3 -3 1 3 4
8.2思路分析
套用模板即可，注意细节。
8.3代码实现
#include <iostream> #include <cstring> #include <queue> using namespace std; const int N=150010; int n,m; int h[N],w[N],e[N],ne[N],idx; //邻接表存储每条边,w[]代表每条边的权重 int dist[N]; //存储1号点到n号点的最短距离 bool st[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; //1号点到1号点（自己）的距离为0 queue<int> q; //队列中存储能被更新的更新后的点（更新后的点，其后的点的距离才会被更新，否则无意义） q.push(1); //将1号点入队 while(q.size()){ 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]){ //如果j不在队列中，则加入 q.push(j); st[j]=true; } } } } if(dist[n]==0x3f3f3f3f) return -3; //如果无法从1号点到达n号点返回-1 return dist[n]; //否则返回从1号点到n号点的距最短离 } int main(){ cin>>n>>m; memset(h,-1,sizeof h); while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } int t=spfa(); if(t==-3) cout<<"impossible"; else cout<<t; return 0; }
题目二
题目链接：852. spfa判断负环
8.4题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中 是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z ，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000,1≤m≤10000,图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 1 2 -1 2 3 4 3 1 -4
输出样例：
Yes
8.5思路分析
套用模板即可，注意细节。
下图来自AcWing官网，作者们如图，侵权删。
8.6代码实现
#include <iostream> #include <cstring> #include <queue> using namespace std; const int N=150010; int n,m; int h[N],w[N],e[N],ne[N],idx; //邻接表存储每条边,w[]代表每条边的权重 int dist[N],cnt[N]; //dist[]存储1号点到n号点的最短距离，cnt[i]存储从1号点到i号点经过的点的数量 bool st[N]; //存储每个点是否已经在队列中，防止队列中存储重复的点 //邻接表加边 void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int spfa(){ queue<int> q; //队列中存储能被更新的更新后的点（更新后的点，其后的点的距离才会被更新，否则无意义） //将所有点入队 for(int i=1;i<=n;i++){ st[i]=true; q.push(i); } while(q.size()){ 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]; cnt[j]=cnt[t]+1; //j经过的点数加1 if(cnt[j]>=n) return true; if(!st[j]){ //如果j不在队列中，则加入 q.push(j); st[j]=true; } } } } return false; } int main(){ cin>>n>>m; memset(h,-1,sizeof h); while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } if(spfa()) cout<<"Yes"; else cout<<"No"; return 0; }
九、floyd算法
核心模板
下图来自AcWing官网，作者们如图，侵权删。
时间复杂度是O(n3)，n表示点数
//初始化 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) d[i][j]=0; else d[i][j]=INF; } } //算法结束后，d[a][b]表示a到b的最短距离 void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } }
题目链接：854. Floyd求最短路
9.1题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤200,1≤k≤n2
1≤m≤20000,图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3
9.2思路分析
套用模板即可，注意细节。
9.3代码实现
#include <iostream> #include <algorithm> using namespace std; const int N=210,INF=1e9; int n,m,q; int d[N][N]; //邻接矩阵 void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ d[i][j]=min(d[i][j],d[i][k]+d[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) d[i][j]=0; else d[i][j]=INF; } } while(m--){ int a,b,w; cin>>a>>b>>w; d[a][b]=min(d[a][b],w); //如果有重边只取最短的 } floyd(); while(q--){ int a,b; cin>>a>>b; if(d[a][b]>INF/2) cout<<"impossible"<<endl; else cout<<d[a][b]<<endl; } return 0; }
十、Prim算法
核心模板
时间复杂度是O(n2+m)，n表示点数，m表示边数
int n; //n表示点数 int g[N][N]; //邻接矩阵，存储所有边 int dist[N]; //存储其他点到当前最小生成树的距离 bool st[N]; //存储每个点是否已经在生成树中 //如果图不连通，则返回INF（值是0x3f3f3f3f），否则返回最小生成树的树边权重之和 int prim(){ memset(dist,0x3f,sizeof dist); int res=0; for(int i=0;i<n;i++){ int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } if(i&&dist[t]==INF) return INF; if(i) res+=dist[t]; st[t]=true; for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]); } return res; }
题目链接：858. Prim算法求最小生成树
10.1题目描述
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500,1≤m≤105,图中涉及边的边权的绝对值均不超过 10000。
输入样例：
4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4
10.2思路分析
套用模板即可，注意理解算法思想，注意细节。
10.3代码实现
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N=510,INF=0x3f3f3f3f; int n,m; int g[N][N]; //邻接矩阵存储所有边 int dist[N]; //存储其他点到当前最小生成树的距离 bool st[N]; //存储每个点是否已经在生成树中 int prim(){ memset(dist,0x3f,sizeof dist); //初始化所有点距离当前最小生成树的距离为正无穷 int res=0; //res存储最小生成树边的权重之和 for(int i=0;i<n;i++){ //循环n次，每次去找当前距离最小生成树的距离最小的点，记录在t中 int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } if(i&&dist[t]==INF) return INF; //如果距离最小仍然是正无穷，说明图并不连通，返回INF if(i) res+=dist[t]; //将距离累加进答案中 for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]); //以当前距离最小的点来更新其他点 st[t]=true; //标记为已在生成树中 } return res; } int main(){ cin>>n>>m; memset(g,0x3f,sizeof g); while(m--){ int a,b,c; cin>>a>>b>>c; g[a][b]=g[b][a]=min(g[a][b],c); } int t=prim(); if(t==INF) cout<<"impossible"<<endl; else cout<<t<<endl; return 0; }
