图论━━最短路问题
2021/11/4 6:10:01
本文主要是介绍图论━━最短路问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 问题
- 单源最短路
- 边权都是正数
- 朴素Dijkstra O(n^2)
- 堆优化的Dijkstra O(mlogn)
- 存在负权边
- Bellman-Ford 算法 O(nm)
- SPFA (没有负环)
- 边权都是正数
- 多源汇最短路
- Floyd 算法 O(n^3)
- 相关题解
问题
图论中的最短路问题,求两个点之间最短距离(路径)的问题;
规定使用n
: 表示点的数量;m
: 表示边的数量;边数m
是顶点数n
的平方级别视为稠密图
- 稠密图使用邻接矩阵存储
- 稀疏图使用邻接表存储(使用数组模拟)
- 只考虑有向图,如果是无向图则每条边存储两次即可;默认只考虑有向图
算法总结:
单源最短路
求从一个点到其他所有点的最短距离,顶点为1,2,3...n
,求顶点1
到其他所有顶点的最短路
边权都是正数
Dijkstra基于贪心算法
- 朴素的Dijkstra算法\(O(n^2)\)适用于稠密图,边数多的情形\(m=n^2\),此时比堆优化好
- 堆优化版Dijkstra算法\(O(mlogn)\)适用于稀疏图,m和n同阶的情形\(m<n^2\)
朴素Dijkstra O(n^2)
稠密图使用邻接矩阵存储
边权是正数时,如果数据出现自环和重边需要预处理:
- 省略自环
- 重边只保存最短的边
距离都是单源点1号点到其他点的距离,使用dist[N]数组保存当前距离;维护一个已经确定最小距离的点的集合S,使用了st[N]数组来标记:
算法思路:
1. 初始化距离 dist[1]=0, dist[i]=\infity 2. for i: 1~n: t <-- 不在S中的点,且距离最近的点 S <-- t(将t加入到S中) 用点t来更新其他点的距离
朴素版Dijkstra算法
Dijkstra求最短路 I#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 510; int n, m; int g[N][N]; // 邻接矩阵 int dist[N]; // 当前顶点1到所有点的距离 bool st[N]; // 是否加入集合S(已知最短距离的点集合) int dijkstra() { // 初始化当前的距离 memset(dist, 0x3f, sizeof dist); dist[1] = 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; st[t] = true; // 更新相邻顶点的距离 for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]); } //判断dist[n] if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(g, 0x3f, sizeof g); while (m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); // 处理多重边 g[a][b] = min(g[a][b], c); } int t = dijkstra(); printf("%d\n", t); }
堆优化的Dijkstra O(mlogn)
稀疏图--使用邻接表存储,方便遍历邻接边,h[N],w[N],e[N],ne[N]
采用stl的priority_queue<PII, vector<PII>, greater<PII>> queue;
存在负权边
Bellman-Ford算法 O(nm)
SPFA 一般:O(m),最坏O(nm); 是Bellman-Ford算法的一个优化, 效率比Bellman-Ford好
但是不是所有的问题都可以用SPFA做,例如 最短路边数<=k的最短路,只能使用Bellman-Ford算法
Bellman-Ford 算法 O(nm)
边的存储方式:只要能够遍历所有的边就可以;
struct edge{ int a,b,w; }edges[N]; for 1:n : for 所有边 a,b,w (a -w-> b) dist[b]=min(dist[b], dist[a]+w(a,b));
思想:因为最短路径 最多为n-1个边 的组合;
松弛n-1次,一定可以松弛完最远的点,得到所有的最短距离
注意: 每次迭代,是对同一个状态进行迭代的,对相同的距离状态进行更新(备份)
说明
- 迭代k次,表示1号点不超过k条边的最短距离
- 如果经过n次迭代,第n次最短路径还有更新,说明这个n条边的路径上n+1个节点,有环,说明有负环,因此,可以判断有负环,但通常使用spfa判断
SPFA (没有负环)
一般是O(m),网格图可能卡成O(nm)
对Bellman-Ford算法的改进, 只有点a变小了,才有可能更新邻点的距离
使用一个队列,存储所有距离变小的点a
- 求没有负环的最短路,直接用队列开优化
- 判断负环,判断路径的长度是否>=n (注意这里需要将所有点预先加入队列)
多源汇最短路
起点和终点都不确定,都任意
Floyd算法 O(n^3) ---基于动态规划原理
都使用有向图来建图,无向图建立2条双向边即可 稠密图使用邻接矩阵g[N][N]存储边;稀疏图使用邻接表,h[N], e[N],ne[N],idx 有负权回路的图,不一定存在最短路,负环不在路径上也可能求到某点的最短路径
Floyd 算法 O(n^3)
* 使用邻接矩阵存储 d[N][N]
;
相关题解
这篇关于图论━━最短路问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29DataGrip使用ssh连接数据库的操作流程
- 2024-05-28SpringBoot3.2更新声明!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据