最短路问题的难点在于建图
我们规定 n:点数 m:边数
一 朴素 Dijkstra 算法 （适应于稠密图，图可以使用邻接矩阵来存）O(n2)
Dijkstra 算法是基于贪心的，每一步都取距离最近的点
1) 初始化 dist[1]=0 dist[...]=+INF 设集合s: 所有当前已确定的点 2) for i:1~n 取出不在 s 中的距离最近的点到 t (这一步可以使用优先队列来优化,就变成了堆优化 Dijkstra 算法) 把 t 放入 s 中, 用 t 去更新其他点的距离
模板题
#include<iostream> #include<cstring> using namespace std; const int NN=510; const int INF=1e9; int n,m; int g[NN][NN]; // 邻接矩阵,用来存储图 int dist[NN]; // d[x]表示为起点到达x点的最短距离 bool st[NN]; // 表示那些点已经走过了 int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1]=0; for(int i=1;i<=n;i++){ // 循环n次 // 找到当前还没有走过且离起点最近的点 t int t=-1; for(int j=1;j<=n;j++){ if(!st[j] && (t==-1 || dist[j]<dist[t])){ t=j; } } st[t]=true; // t已经走过了, 做一个标记 // 以 t 为根据, 尝试更新其他点, 看一下是直接到j点近, 还是经过t点到j点近 // 起点 ----> j // | ^ // v | // ----t----- for(int j=1;j<=n;j++){ dist[j]=min(dist[j], dist[t]+g[t][j]); } } if(dist[n]>=INF) return -1; else return dist[n]; } int main(){ cin>>n>>m; memset(g, 0x3f, sizeof g); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d", &x, &y, &z); g[x][y]=min(g[x][y],z); // 图中可能有重边，就去路径最短的点 } cout<<dijkstra()<<endl; return 0; }
其他题目
2662. 前往目标的最小代价 - 力扣（LeetCode）
二 堆优化 Dijkstra 算法 （适应于稀疏图，图用邻接表来存）O(m⋅logn)
1) 初始化 dist[1]=0 dist[...]=+INF 设集合s: 所有当前已确定的点 2) queue <- 起点 while queue 不为空 从优先队列 queue 中取出距离最小的点 t 把 t 放入 s 中, 用 t 去更新其他点x的距离, 如果 x 发生了更新, 才把放入 queue
模板题 850. Dijkstra 求最短路 II - AcWing 题库
#include<iostream> #include<vector> #include<cstring> #include<queue> using namespace std; typedef pair<int,int> PII; const int NN=1.5e5+10; vector<PII> g[NN]; int dist[NN]; bool st[NN]; int n,m; // heap中的pair : first 某点到起点的距离 // : second 这个点的编号 // g 中的pair : first 某条边的长度 // : second 这条边的终点编号 int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1]=0; priority_queue<PII, vector<PII>, greater<PII>> heap; // 小顶堆, 使用小顶堆来快速找到满足条件的t, // 而不是像朴素Dijkstra那样去循环 heap.push({0,1}); while(!heap.empty()){ PII t=heap.top(); heap.pop(); int idx=t.second; if(st[idx]) continue; st[idx]=true; for(auto it: g[idx]){ int nidx=it.second; int nd=it.first; // 只有发生更新的点才入队,因为只有发生更新的点的后继节点才有发生更新的可能 if(dist[idx]+nd<dist[nidx]){ dist[nidx]=dist[idx]+nd; heap.push({dist[nidx], nidx}); } } } return dist[n]>=0x3f3f3f3f ? -1 : dist[n]; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d", &x,&y,&z); g[x].push_back({z,y}); // 把距离放在pair的first位置上,方便在堆中排序 } cout<<dijkstra()<<endl; return 0; }
三 Bellman-Ford 算法 （存边的方式会比较灵活，可以使用结构体） O(n⋅m)
Bellmain-Ford 算法可以处理负权边, 但是有负权边则最短路径不一定存在
有边数限制的话只能用 Bellman-Ford 算法
1) 初始化 dist[1]=0 dist[...]=+INF 2) for n 次 备份 dist -> backup for 所有边 a,b,w (a--w->b) dist[b] = min(dist[b], backup[a]+w)
为了保证一定使用的是上次迭代的数据来更新本次迭代, 这里一定要备份,否则有可能发生串联混乱
迭代 k 次表示经过不超过 k 条边, 如果迭代 n 次时, dist 还有更新, 说明有一条路径上有 n 条边, 而无环图最多有 n-1 条边, 有抽屉原理可知路径上一定有环
模板题 853. 有边数限制的最短路 - AcWing 题库
#include<iostream> #include<cstring> using namespace std; const int NN=1e4+10; struct Edge{ int a, b, w; } edges[NN]; int n,m,k; int dist[NN]; int backup[NN]; void bellman_ford(){ memset(dist, 0x3f, sizeof dist); dist[1]=0; for(int i=1;i<=k;i++){ // 把最短路径的边数限制为k memcpy(backup, dist, sizeof dist); for(int j=1;j<=m;j++){ int a,b,w; 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) cout<<"impossible"<<endl; else cout<<dist[n]<<endl; } // bellman-ford 算法可以解决有边数限制的问题 int main(){ cin>>n>>m>>k; for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d", &x,&y,&z); edges[i]={x,y,z}; } bellman_ford(); return 0; }
四 SPFA 算法 (是对 Bellman-Ford 算法的改进, SPFA 算法要求不能有负环) O(m) 最坏 O(n⋅m)
在 Bellman-Ford 算法中 dist[b] = min(dist[b], backup[a]+w) 只有 backup[a] 变小, dist[b] 才有可能变小,可以在一个 queue 中存所有变小的 a 也就是说只有一个点变小了, 这个点的后继点才有可能变小
1) 初始化 dist[1]=0 dist[...]=+INF 使用一个 bool st[] 来记录某个点是否在 queue 中 2) queue <- 起点 while queue 不空 (1) t <- q.front() q.pop() (2) 更新 t 的所有出边 t--w->b 如果 b 发生了更新且不在 queue 中, 则 queue <- b
可以看出 SPFA 算法不断只有当所有点都不发生更新的时候才会停止, 如果图中有负环的话, 则会始终有点发生更新, 就会产生死循环
模板题 851. spfa 求最短路 - AcWing 题库
#include<iostream> #include<queue> #include<vector> #include<cstring> using namespace std; typedef pair<int,int> PII; const int NN=1e5+10; int n,m; vector<PII> g[NN]; int dist[NN]; bool st[NN]; void spfa(){ memset(dist, 0x3f, sizeof dist); dist[1]=0; queue<PII> que; que.push({0,1}); // 起点入队 st[1]=true; while(!que.empty()){ auto t=que.front(); que.pop(); int idx=t.second; int d=t.first; st[idx]=false; // 出队的点 st 还会被重新设为 false, 这就意味着后面这个点还有重新入队的机会, 这一点与 Dijkstra 不同 for(auto it:g[idx]){ int nidx=it.second; int nd=it.first; if(dist[nidx]>dist[idx]+nd){ dist[nidx]=dist[idx]+nd; // 只有发生更新而且不在que中的点才能入队 if(!st[nidx]){ que.push({dist[nidx], nidx}); st[nidx]=true; } } } } if(dist[n]>=0x3f3f3f3f/2){ // 因为存在负权边,所以要把无穷大的条件放宽一点 cout<<"impossible"<<endl; }else{ cout<<dist[n]<<endl; } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d", &x,&y,&z); g[x].push_back({z,y}); } spfa(); return 0; }
SPFA 算法也可以用来判断是否存在负环
1) dist[x] 最短距离 cnt[x] 边数 2) 我们 在更新 dist[x] 的时候， 同时记录 cnt[x] 当有 cnt[x]>=n 时，说明存在负环
五 Floyd 算法 (可以用来解决多源汇最短路问题 使用邻接矩阵来存所有的边)
1) 初始化 dist[i,i]=0 dist[i,j]=+INF 2) for k : 1~n for i : 1~n for j : 1~n d[i,j] = min(d[i,j], d[i,k]+d[k,j])
公式d[i,j] = min(d[i,j], d[i,k]+d[k,j])是由公式d[k,i,j]=d[k-1,i,k]+d[k-1,k,j]优化空间而来
模板题 854. Floyd 求最短路 - AcWing 题库
#include<iostream> #include<cstring> using namespace std; const int NN=210; int n,m,k; int dist[NN][NN]; // dist[i][j]记录从i到j点的最短距离 void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } } } } int main(){ cin>>n>>m>>k; memset(dist, 0x3f, sizeof dist); for(int i=1;i<=n;i++){ dist[i][i]=0; } for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); dist[x][y]=min(dist[x][y],z); } floyd(); for(int i=1;i<=k;i++){ int x,y; scanf("%d%d",&x,&y); if(dist[x][y]>=0x3f3f3f3f/2){ cout<<"impossible"<<endl; } else{ cout<<dist[x][y]<<endl; } } return 0; }
