最短路
定义
(还记得这些定义吗?在阅读下列内容之前,请务必了解 图论相关概念 中的基础部分。)
- 路径
- 最短路
- 有向图中的最短路、无向图中的最短路
- 单源最短路、每对结点之间的最短路
记号
为了方便叙述,这里先给出下文将会用到的一些记号的含义。
为图上点的数目, 为图上边的数目; 为最短路的源点; 为 点到 点的 实际 最短路长度; 为 点到 点的 估计 最短路长度。任何时候都有 。特别地,当最短路算法终止时,应有 。 为 这一条边的边权。
性质
对于边权为正的图,任意两个结点之间的最短路,不会经过重复的结点。
对于边权为正的图,任意两个结点之间的最短路,不会经过重复的边。
对于边权为正的图,任意两个结点之间的最短路,任意一条的结点数不会超过
Floyd 算法
是用来求任意两个结点之间的最短路的。
复杂度比较高,但是常数小,容易实现(只有三个 for
)。
适用于任何图,不管有向无向,边权正负,但是最短路必须存在。(不能有个负环)
实现
我们定义一个数组 f[k][x][y]
,表示只允许经过结点
很显然,f[n][x][y]
就是结点
接下来考虑如何求出 f
数组的值。
f[0][x][y]
:f[0][x][y]
什么时候应该是
f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])
(f[k-1][x][y]
,为不经过 f[k-1][x][k]+f[k-1][k][y]
,为经过了
上面两行都显然是对的,所以说这个做法空间是
1 2 3 4 5 6 7 |
|
1 2 3 4 |
|
因为第一维对结果无影响,我们可以发现数组的第一维是可以省略的,于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])
。
证明第一维对结果无影响
我们注意到如果放在一个给定第一维 k
二维数组中,f[x][k]
与 f[k][y]
在某一行和某一列。而 f[x][y]
则是该行和该列的交叉点上的元素。
现在我们需要证明将 f[k][x][y]
直接在原地更改也不会更改它的结果:我们注意到 f[k][x][y]
的涵义是第一维为 k-1
这一行和这一列的所有元素的最小值,包含了 f[k-1][x][y]
,那么在原地进行更改也不会改变最小值的值,因为如果将该三维矩阵压缩为二维,则所求结果 f[x][y]
一开始即为原 f[k-1][x][y]
的值,最后依然会成为该行和该列的最小值。
故可以压缩。
1 2 3 4 5 6 7 |
|
1 2 3 4 |
|
综上时间复杂度是
应用
给一个正权无向图,找一个最小权值和的环。
首先这一定是一个简单环。
想一想这个环是怎么构成的。
考虑环上编号最大的结点
f[u-1][x][y]
和
在 Floyd 的过程中枚举
时间复杂度为
已知一个有向图中任意两点之间是否有连边,要求判断任意两点是否连通。
该问题即是求 图的传递闭包。
我们只需要按照 Floyd 的过程,逐个加入点判断一下。
只是此时的边的边权变为
再进一步用 bitset 优化,复杂度可以到
1 2 3 4 |
|
Bellman–Ford 算法
Bellman–Ford 算法是一种基于松弛(relax)操作的最短路算法,可以求出有负权的图的最短路,并可以对最短路不存在的情况进行判断。
在国内 OI 界,你可能听说过的「SPFA」,就是 Bellman–Ford 算法的一种实现。
过程
先介绍 Bellman–Ford 算法要用到的松弛操作(Dijkstra 算法也会用到松弛操作)。
对于边
这么做的含义是显然的:我们尝试用
Bellman–Ford 算法所做的,就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环,就对图上所有的边都尝试进行一次松弛操作,当一次循环中没有成功的松弛操作时,算法停止。
每次循环是
在最短路存在的情况下,由于一次松弛操作会使最短路的边数至少
但还有一种情况,如果从
负环判断中存在的常见误区
需要注意的是,以
因此如果需要判断整个图上是否存在负环,最严谨的做法是建立一个超级源点,向图上每个节点连一条权值为 0 的边,然后以超级源点为起点执行 Bellman–Ford 算法。
实现
参考实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
队列优化:SPFA
即 Shortest Path Faster Algorithm。
很多时候我们并不需要那么多无用的松弛操作。
很显然,只有上一次被松弛的结点,所连接的边,才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」,就能只访问必要的边了。
SPFA 也可以用于判断
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
|
虽然在大多数情况下 SPFA 跑得很快,但其最坏情况下的时间复杂度为
Bellman–Ford 的其他优化
除了队列优化(SPFA)之外,Bellman–Ford 还有其他形式的优化,这些优化在部分图上效果明显,但在某些特殊图上,最坏复杂度可能达到指数级。
- 堆优化:将队列换成堆,与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
- 栈优化:将队列换成栈(即将原来的 BFS 过程变成 DFS),在寻找负环时可能具有更高效率,但最坏时间复杂度仍然为指数级。
- LLL 优化:将普通队列换成双端队列,每次将入队结点距离和队内距离平均值比较,如果更大则插入至队尾,否则插入队首。
- SLF 优化:将普通队列换成双端队列,每次将入队结点距离和队首比较,如果更大则插入至队尾,否则插入队首。
- D´Esopo–Pape 算法:将普通队列换成双端队列,如果一个节点之前没有入队,则将其插入队尾,否则插入队首。
更多优化以及针对这些优化的 Hack 方法,可以看 fstqwq 在知乎上的回答。
Dijkstra 算法
Dijkstra(/ˈdikstrɑ/或/ˈdɛikstrɑ/)算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现,1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。
过程
将结点分成两个集合:已确定最短路长度的点集(记为
初始化
然后重复这些操作:
- 从
集合中,选取一个最短路长度最小的结点,移到 集合中。 - 对那些刚刚被加入
集合的结点的所有出边执行松弛操作。
直到
时间复杂度
有多种方法来维护 1 操作中最短路长度最小的结点,不同的实现导致了 Dijkstra 算法时间复杂度上的差异。
- 暴力:不使用任何数据结构进行维护,每次 2 操作执行完毕后,直接在
集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 ,1 操作总时间复杂度为 ,全过程的时间复杂度为 。 - 二叉堆:每成功松弛一条边
,就将 插入二叉堆中(如果 已经在二叉堆中,直接修改相应元素的权值即可),1 操作直接取堆顶结点即可。共计 次二叉堆上的插入(修改)操作, 次删除堆顶操作,而插入(修改)和删除的时间复杂度均为 ,时间复杂度为 。 - 优先队列:和二叉堆类似,但使用优先队列时,如果同一个点的最短路被更新多次,因为先前更新时插入的元素不能被删除,也不能被修改,只能留在优先队列中,故优先队列内的元素个数是
的,时间复杂度为 。 - Fibonacci 堆:和前面二者类似,但 Fibonacci 堆插入的时间复杂度为
,故时间复杂度为 ,时间复杂度最优。但因为 Fibonacci 堆较二叉堆不易实现,效率优势也不够大1,算法竞赛中较少使用。 - 线段树:和二叉堆原理类似,不过将每次成功松弛后插入二叉堆的操作改为在线段树上执行单点修改,而 1 操作则是线段树上的全局查询最小值。时间复杂度为
。
在稀疏图中,
正确性证明
下面用数学归纳法证明,在 所有边权值非负 的前提下,Dijkstra 算法的正确性2。
简单来说,我们要证明的,就是在执行 1 操作时,取出的结点
初始时
接下来用反证法。
设
于是一定存在路径
因为在
下面证明
因此我们证明了,1 操作每次取出的点,其最短路均已经被确定。命题得证。
注意到证明过程中的关键不等式
实现
这里同时给出
暴力实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
优先队列实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
Johnson 全源最短路径算法
Johnson 和 Floyd 一样,是一种能求出无负环图上任意两点间最短路径的算法。该算法在 1977 年由 Donald B. Johnson 提出。
任意两点间的最短路可以通过枚举起点,跑
注意到堆优化的 Dijkstra 算法求单源最短路径的时间复杂度比 Bellman–Ford 更优,如果枚举起点,跑
但 Dijkstra 算法不能正确求解带负权边的最短路,因此我们需要对原图上的边进行预处理,确保所有边的边权均非负。
一种容易想到的方法是给所有边的边权同时加上一个正数
但这样的方法是错误的。考虑下图:
但假如我们把每条边的边权加上
新图上
Johnson 算法则通过另外一种方法来给每条边重新标注边权。
我们新建一个虚拟节点(在这里我们就设它的编号为
接下来用 Bellman–Ford 算法求出从
假如存在一条从
接下来以每个点为起点,跑
一开始的 Bellman–Ford 算法并不是时间上的瓶颈,若使用 priority_queue
实现 Dijkstra 算法,该算法的时间复杂度是
正确性证明
为什么这样重新标注边权的方式是正确的呢?
在讨论这个问题之前,我们先讨论一个物理概念——势能。
诸如重力势能,电势能这样的势能都有一个特点,势能的变化量只和起点和终点的相对位置有关,而与起点到终点所走的路径无关。
势能还有一个特点,势能的绝对值往往取决于设置的零势能点,但无论将零势能点设置在哪里,两点间势能的差值是一定的。
接下来回到正题。
在重新标记后的图上,从
化简后得到:
无论我们从
为了方便,下面我们就把
上面的新图中
到这里我们的正确性证明已经解决了一半——我们证明了重新标注边权后图上的最短路径仍然是原来的最短路径。接下来我们需要证明新图中所有边的边权非负,因为在非负权图上,Dijkstra 算法能够保证得出正确的结果。
根据三角形不等式,图上任意一边
这样,我们就证明了 Johnson 算法的正确性。
不同方法的比较
最短路算法 | Floyd | Bellman–Ford | Dijkstra | Johnson |
---|---|---|---|---|
最短路类型 | 每对结点之间的最短路 | 单源最短路 | 单源最短路 | 每对结点之间的最短路 |
作用于 | 任意图 | 任意图 | 非负权图 | 任意图 |
能否检测负环? | 能 | 能 | 不能 | 能 |
时间复杂度 |
注:表中的 Dijkstra 算法在计算复杂度时均用 priority_queue
实现。
输出方案
开一个 pre
数组,在更新距离的时候记录下来后面的点是如何转移过去的,算法结束前再递归地输出路径即可。
比如 Floyd 就要记录 pre[i][j] = k;
,Bellman–Ford 和 Dijkstra 一般记录 pre[v] = u
。
参考资料与注释
-
《算法导论(第 3 版中译本)》,机械工业出版社,2013 年,第 384 - 385 页。 ↩
本页面最近更新:2024/8/22 00:35:15,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:StudyingFather, dkz051, du33169, lingkerio, abc1763613206, AljcC, AndrewWayne, Anguei, ArcticLampyrid, asxzt, boristown, CCXXXI, ChungZH, countercurrent-time, Early0v0, Enter-tainer, Error-Eric, FinBird, greyqz, H-J-Granger, Haohu Shen, hensier, iamtwz, ImpleLee, Ir1d, isdanni, Kaiser-Yang, ksyx, LiserverYang, mcendu, Menci, mgt, miaotony, MingqiHuang, NachtgeistW, Nanarikom, ouuan, ouuan, PeterlitsZo, renbaoshuo, Reqwey, shawlleyw, Steaunk, SukkaW, Tiphereth-A, TrisolarisHD, wplf, Xeonacid, Yanjun-Zhao, zzjjbb
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用