最短路算法
2022/3/20 11:27:56
本文主要是介绍最短路算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
单源最短路
正权边
Dijkstra算法 O(n^2)
每次通过已知最短距离来更新到其他点的最短路
注意出现重边要进行比较
#include<iostream> #include<algorithm> using namespace std; const int N = 1e5+10; int g[N][N];//邻接矩阵 int dist[N];//源点到其他点的距离 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[j] < dist[t])) 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]; }
堆优化的Dijkstra算法 O(mlogn)
如果是稀疏图,点数量多,遍历的时候就会超时,所以用邻接表存储,每次取最短距离的步骤可以用最小堆优化
#include <iostream> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 1e5 + 10; int n; int h[N], w[N], ne[N], e[N], idx; int dist[N]; int st[N]; int Dijkstra() { memset(h, -1, sizeof h); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); while (heap.size()) { PII t = heap.top(); 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]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { return 0; }
负权边
Bellman-ford算法 O(nm)
Dijkstra算法无法处理有负权边的图
一层一层的去更新
有限步数的条件下只能用Bellman-ford算法
int n, m; // n表示点数,m表示边数 int dist[N]; // dist[x]存储1到x的最短路距离 struct Edge // 边,a表示出点,b表示入点,w表示边的权重 { int a, b, w; }edges[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]; }
spfa算法 O(m)
队列优化的Bellman_ford算法
可以用来判断是否有负权回路,需要时只需要加一个cnt数组来记录点数,如果点数>n就说明存在负权环
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]; if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入 { q.push(j); st[j] = true; } } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
多源汇最短路
Floyd算法
初始化: 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]); }
这篇关于最短路算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行