最短路
2022/3/22 6:30:04
本文主要是介绍最短路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最短路难点不在于证明,在于建图,把一个问题抽象成图,如何定义边,如何定义图
Dijkstra迪杰斯特拉
本质,是不断刷新起点与其他各个顶点之间的 “距离表”。
- 初始化距离
一号结点的距离为零,其他结点的距离设为无穷大(看具体的题)。 - 循环n次,每一次将集合S之外距离最短X的点加入到S中去(这里的距离最短指的是距离1号点最近。点X的路径一定最短,基于贪心,严格证明待看)。然后用点X更新X邻接点的距离。
int g[N][N]; // 存储每条边 int dist[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 ++ ) // 循环n-1次,每个号都遍历一次(除了最后一个n) { int t = -1; // 在还未确定最短路的点中,寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 得到距离最近的一个号 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); // 用t更新其他点的最短距离 st[t] = true; //进行标记,下次不取这个号 } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
堆优化版Dijkstra(适合稀疏图)
堆优化版的dijkstra是对朴素版dijkstra进行了优化,在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。
- 一号点的距离初始化为零,其他点初始化成无穷大。
- 将一号点放入堆中。
- 不断循环,直到堆空。每一次循环中执行的操作为:
弹出堆顶(与朴素版diijkstra找到S外距离最短的点相同,并标记该点的最短路径已经确定)。
用该点更新临界点的距离,若更新成功就加入到堆中。
typedef pair<int, int> PII; int n; // 点的数量 int h[N], w[N], e[N], ne[N], 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; 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]; }
bellman - ford
用结构体储存,方便遍历所有边。
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 ++ ) //一共走n步数 { 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算法
bellman-ford
算法很傻,在该算法中,我们需要遍历很多次所有的边,在遍历的过程中,只有满足dist[b] > dist[a] + w
这个条件,距离才会发生改变。SPFA
算法进行了改进,只有dist[a]
发生变化,才遍历和他相关的边。
Bellman_ford
算法会遍历所有的边,但是有很多的边遍历了其实没有什么意义,我们只用遍历那些到源点距离变小的点所连接的边即可,只有当一个点的前驱结点更新了,该节点才会得到更新;因此考虑到这一点,我们将创建一个队列每一次加入距离被更新的结点。
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到1号点的最短距离 bool st[N]; // 存储每个点是否在队列中 // 求1号点到n号点的最短路距离 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]; //这里判断dist[j]是否发生变化,变化了才可以入队,不能用min if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; //只有j的距离变化了,才可以入队,故不可写在外面 if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入 { q.push(j); st[j] = true; } } } } return dist[n]; }
SPFA判断负环
就是在原有的spfa
模板上加个cnt[N]
用来记录每个点的边数
如果这个边数超过n个,那么一定存在负环
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; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环 if (cnt[j] >= n) return true; if (!st[j]) { q.push(j); st[j] = true; } } } } return false; }
spfa、bellman-ford和djikstra三者的区别
首先,三者都是用来求最短路,但是思想和复杂度不相同。
bellman-ford 和spfa的区别
1.Bellman-ford
算法中,循环n次,每次遍历m条边,每次遍历的时候,把入度的点的距离更新成最小。
然而,这样就循环遍历了很多用不到的边。比如第一次遍历,只有第一个点的临边是有效的。
2.因此,spfa
算法中,采用邻接表的方式,只用到有效的点(更新了临边的点),直到每个点都是最短距离为止。采用队列优化的方式存储每次更新了的点,每条边最多遍历一次。如果存在负权回路,从起点1出发,回到1距离会变小, 会一直在三个点中循环。
Question:
不用队列,遍历所有的点可以吗?
Ans:
似乎不行,因为是更新了点之后,这个点的临边才可以用,如果没有更新到循环的点,那么循环的点也是不可用的。
spfa和dijkstra的区别:
st
用来检验队列中是否有重复的点
spfa
从队列中使用了当前的点,会把该点pop
掉,状态数组st[i] = false
(说明堆中不存在了) ,更新临边之后,把临边放入队列中, 并且设置状态数组为true,表示放入队列中 。如果当前的点距离变小,可能会再次进入队列,因此可以检验负环:
每次更新可以记录一次,如果记录的次数 > n,代表存在负环(环一定是负的,因为只有负环才会不断循环下去)。
st
是一个集合,不是检验队列中的点。
dijkstra
使用当前点更新临边之后,把该点加入到一个集合中,使用该点更新临边,并把临边节点和距离起点的距离置入堆中(不设置状态数组)。下一次从堆中取最小值,并把对应的节点放入集合中,继续更新临边节点,直到所有的点都存入集合中。因此dijkstra
不判断负环。
从上述描述中能看出,dijkstra
存放节点的堆,具有单调性,而spfa
的队列不需要具有单调性。
Floyd算法
用于:给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。
初始化: 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() { //从i出发,只经过k,到达j的距离 //以k为中继点,k是阶段 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漏洞挖掘-有意思的命令执行