最短路问题汇总
-
最短路
-
单源最短路
- 求从一个点到其他所有点的最短距离
-
所有边权是正数
- 朴素Dijkstra算法 O(n^2)
- 用于稠密图 m >= n
- 步骤：
- dist[i]：每个点离起点的距离
- S：已经确定最短距离的点
- V：没有确定最短距离的点
- 初始化所有点的距离dist[起点] = 0；dist[其他点] = inf
- 循环找V中离起点最近的点t
- 将t放入S中
- 用t的距离更新其他点的距离
- 代码：
const int N = 510; int g[N][N];//稠密图用邻接矩阵 int dist[N];//到原点的距离 int st[N];//标记数组 int dijkstra(){ //初始化距离 memset(d, 0x3f, sizeof d); d[1] = 0; //遍历n次每次找距离原点最近的节点 for(int i = 1; i <= n; ++ i){ //在n个接节点中找 int t = 0; for(int j = 1; j <= n; ++ j) if(!st[j] && (!t || d[t] > d[j]) t = j; //找到了 } st[t] = 1; //标记已经找到最短距离 //更新所有节点的距离 for(int j = 1; j <= n; ++ j) d[j] = min(d[j], d[t] + g[t][j]); if(d[n] == 0x3f3f3f3f) return -1;//1-n不连通 else return d[n]; //返回1-n的最短距离 } //注意初始化边权为inf memset(g, 0x3f, sizeof g); //输入边权 while(m -- ){ int a, b, c; cin >> a >> b >> c; //有重边就取最小边权 g[a][b] = min(g[a][b], c);
- 堆优化Dijkstra算法 O(mlogn)
- 用于稀疏图 m <= n
- 用堆存储每个节点的距离，堆顶元素就是离原点距离最近的节点
- 代码：
const int N = 1.5e5 + 10; typedef pair<int, int> PII; int st[N]; int h[N], e[N], ne[N], idx = 1; int d[N], w[N];//w[i]边i的权值 int n, m; void add(int x, int y, int z){ e[idx] = y; ne[idx] = h[x]; h[x] = idx; w[idx] = z; idx ++ ; } int dijkstra(){ //初始化 memset(d, 0x3f, sizeof d); d[1] = 0; priority_queue<PII, vector<PII>, greater<PII> > q;//小根堆 q.push({0, 1});//起点入堆 while(q.size()){ auto t = q.top();//取堆顶元素，离起点最近的节点 q.pop(); int dist = t.first, node = t.second;//获取信息 if(st[node]) continue;//已经求出最短距离就跳过 st[node] = 1; for(int i = h[node]; i; i = ne[i]){ int j = e[i];//遍历相连的所有节点 if(d[j] > dist + w[i]){//更新最短距离 d[j] = dist + w[i]; q.push({d[j], j});//入堆 } } } if(d[n] == 0x3f3f3f3f) return -1; else return d[n]; }
- 朴素Dijkstra算法 O(n^2)
-
存在边权是负数
- Bellman-Ford算法 O(nm)
- 能够找到有边数限制的最短路径
- 可以判断图中有无负权回路
- 当外层循环执行n次（最短路更新了n次），说明最大有n条边构成了最短路，即有n+1个节点构成了最短路，根据鸽巢原理知，路中必有两个相同的节点，即路中有回路，又最短路更新的前提是最短路可以变得更小，所以该回路一定构成负权回路
- 当有边数限制时，即使图中有负环也无所谓，因为负环不能被无限选择
- 代码：
const int N = 510; const int M = 1e4 + 10; struct egde{ //边 int u, v, w; }edges[M]; int d[N], backup[N];//备份数组 int n, m, k; int ballmen_ford(){ //初始化 memset(d, 0x3f, sizeof d); d[1] = 0; for(int i = 1; i <= k; ++ i){ //k条边限制 memcpy(backup, d, sizeof d); //存备份 for(int j = 1; j <= m; ++ j){ //遍历每一条边 int u = edges[j].u; //获取信息 int v = edges[j].v; int w = edges[j].w; d[v] = min(d[v], backup[u] + w); //利用备份更新 } } if(d[n] > 0x3f3f3f3f / 2) return -N; else return d[n]; } int main(){ cin >> n >> m >> k; for(int i = 1; i <= m; ++ i){ int x, y, z; cin >> x >> y >> z; edges[i] = {x, y, z}; } int t = ballmen_ford(); if(t == -N) cout << "impossible"; else cout << t << endl; return 0; }
- SPFA算法 一般O(m)最坏O(nm)
- 相当于优化版的ballmen_ford
- 可以用于判断图中是否有负权回路
- 设置cnt[i]数组，表示最短路从起点到i的边的数量，当某时刻边的数量>=n，说明路中有回路
- 代码：
const int N = 1e5 + 10; int h[N], e[N], ne[N], idx = 1; int d[N], w[N], cnt[N];//cnt[i]数组表示从起点到i的最短路中的边的数量 int st[N]; //标记元素是否已经进入队列 int n, m; void add(int a, int b, int z){ e[idx] = b; ne[idx] = h[a]; h[a] = idx; w[idx] = z; idx ++ ; } bool spfa(){ queue<int> q; for(int i = 1; i <= n; ++ i){//所有节点入队，负环有可能不是从1-n路径上的，所以以每个节点为起点的路径都要检查 q.push(i); st[i] = 1;//标记已入队 } while(q.size()){ int t = q.front(); q.pop(); st[t] = 0;//出队 for(int i = h[t]; i; i = ne[i]){ int j = e[i]; if(d[j] > d[t] + w[i]){ d[j] = d[t] + w[i]; //更新 cnt[j] = cnt[t] + 1;//边数加一 if(cnt[j] >= n) return true;//边数>=n时，说明有环 if(!st[j]){ q.push(j);//只将更新过的元素入队 st[j] = 1; } } } } return false; } int main(){ cin >> n >> m; while(m -- ){ int x, y, z; cin >> x >> y >> z; add(x, y, z); } if(spfa()) cout << "Yes"; else cout << "No"; return 0; }
- d[v] = min(d[v], backup[u] + w); //利用备份更新，这句话存在很多无效更新。只有当u更新过后，d[v]的更新才有效，因此只需要将更新过的节点放入一个集合，每次只用在集合中取元素去更新它邻接的节点
- 有些正权图也可以用SPFA算法
- 代码：
const int N = 1e5 + 10; int h[N], e[N], ne[N], idx = 1; int d[N], w[N]; int st[N]; //标记元素是否已经进入队列 int n, m; void add(int a, int b, int z){ e[idx] = b; ne[idx] = h[a]; h[a] = idx; w[idx] = z; idx ++ ; } int spfa(){ //初始化 memset(d, 0x3f, sizeof d); d[1] = 0; //队列存储更新过距离的节点 queue<int> q; q.push(1); st[1] = 1;//标记已入队 while(q.size()){//循环 int t = q.front(); q.pop(); st[t] = 0; for(int i = h[t]; i; i = ne[i]){ int j = e[i]; if(d[j] > d[t] + w[i]){ d[j] = d[t] + w[i]; //更新 if(!st[j]){ q.push(j);//只将更新过的元素入队 st[j] = 1; } } } } if(d[n] > 0x3f3f3f3f / 2) return -N; else return d[n]; } int main(){ cin >> n >> m; while(m -- ){ int x, y, z; cin >> x >> y >> z; add(x, y, z); } int t = spfa(); if(t == -N) cout << "impossible"; else cout << t; return 0; }
- 存在负权边的图中存在最短路的话，图中一定不能有负权回路，除非最短路边数有限制，否则一直沿着回路绕，路径越来越小，直到最短路为负无穷
- Bellman-Ford算法 O(nm)
-
多源汇最短路
- 源点起点，汇点终点，起点与终点任意选取
- Floyd算法 O(n^3)
- 可以处理有负权的图，但不能处理有负权回路的图
- 代码：
const int N = 210; const int M = 2e4 + 10; const int INF = 0x3f3f3f3f; int d[N][N];//存储两点间的最短路 int n, m, k; 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 >> k; //初始化 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 x, y, z; cin >> x >> y >> z; d[x][y] = min(d[x][y], z);//去重边 } floyd(); while(k -- ){ int u, v; cin >> u >> v; int t = d[u][v]; if(t > INF / 2) cout << "impossible" << endl; else cout << t << endl; } return 0; }
-
热门相关：我的治愈系游戏 异世修真邪君 买妻种田：山野夫君，强势宠！ 大妆 后福