图论最短路

· · 算法·理论

1：最短路算法

Dijkstra 算法

Dijkstra算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解非负权图上单源最短路径的算法。

算法步骤

将所有节点分为已确定最短距离和未确定最短距离两个部分。

从已知最短距离的节点中，更新相邻的（即这两个点有直接边连接）未确定最短距离的节点。

直到没有点未确定最短距离。

初始化：dis_s\gets 0,dis_i\gets +∞），i\ne s。

Dijkstra 算法之所以不支持求解负权图，是因为在非负权图中，只要一直走，最短路一定会增大，但是在负权图中就不适用了。

看了这张图你或许就能明白了：

起点为 1，终点为 3。

按照 Dijkstra 的思想，我们首先将 dis_2 更新为 100，dis_3 更新为 10。

然后选择 3 更新周围节点，但是它没有直接边与其他边连接，所以 dis_3=10。

而实际上 dis_3=-5。

也就是说，在有负权边的图中，经过的边数多，最短路不一定更大。

或许有人会说，将所有边权同时加上同一个正整数 x（x\ge 最小边权），使得所有边权均为正整数，然后同时维护经过了几条边 s，最后将得出来的最短路减去 x\times s 不就可以了吗？

其实这是错误的，比如这张图：

这张图的最短路径为：1 -> 4 -> 5 -> 3。

但是我们将所有边权 +7 后：

最短路径变为：1 -> 2 -> 3。

可以发现，在加上数值之后，原先的最短路不一定最优了。

我们需要以另一种方式加上数值。

请参考 Johnson 全源最短路径算法。

Bellman-Ford 算法

Bellman–Ford 算法是一种基于松弛操作的最短路算法，可以求出有负权边的图的最短路，并可以对最短路不存在的情况进行判断。

该算法由理查德·贝尔曼（Richard Bellman）和莱斯特·福特提出。

算法步骤

不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环为 O(m)，可以证明，最多只会进行 n-1 次（最短路径最长不会经过超过 n-1 条边），所以总时间复杂度为 O(nm)。

负环

一张有向图中的环的边权之和为负数。

最短路算法中不能出现负环，最长路算法中不能出现正环。

比方说下面这张图：

从 5 出发，每转上一圈，最短路就会减少 2，然后你就会转上 1,2,3,\ldots,∞ 圈。

所以说有负环的有向图是没有最短路的（有负环的有向图跑最短路把天河二号跑炸了都跑不出来）。

怎么判断呢？

Bellman-Ford 算法中如果算法进行了 n-1 次后还能更新，说明存在负环。

注意：有向图中不一定所有点都能找到负环（假设图中存在负环），例如从上图中 4 开始是找不到负环的。比较常见的一个做法是建立一个超级源点 0，然后跟其他 n 个点连接一条权值为 0 的有向边，再从 0 开始查找负环。

优化版 Bellman-Ford（SPFA）算法

你会发现，Bellman-Ford 运行得超级慢（时间复杂度 O(nm) 还不慢吗）。

所以怎么优化呢？

我们发现只有更新过的点，才能直接用来更新。

用队列记录上次更新点的编号，每个点最多会重复入队 n-1 次（可以用来判负环）。

随后你会发现 Bellman-Ford 算法加上队列优化运行时间跟没优化貌似没什么区别……

还有一个很重要的点：如果这个点已经在队列中了，就不用再进行入队了，因为它迟早会更新。

所以开个 vis 数组标记一下该元素有没有在队列中。

队列只是基础，vis 才是关键。

SPFA 算法的缺点

你可能在国内 OI 圈听说过这句话：“关于 SPFA，它死了”。

那为啥说它“死了”呢？

出题人卡 SPFA 通常会用到两种图：

  1. 菊花图，你可以理解为深度仅为 2 的树。
  2. 网格图。

比如说有这么一张有向图：

总共更新 $\dfrac{n}{2}$ 次，这时候时间复杂度跟 Bellman-Ford 差不多（问了几个大模型都是这么说）。 数据小可能还不太会体现出来，数据一大就直接……（~~上香吧，没救了~~）。 所以能不要用 SPFA 就不要用 SPFA 啊 QwQ。 P.S.：据说还有个 SPFA 的优化方法，但是我不会。 ## Floyd 算法 Floyd 算法是一种用于解决图中最短路径问题的经典算法，由美国计算机科学家罗伯特·弗洛伊德于1962年提出。 该算法基于动态规划的思想，用 $O(n^3)$ 的时间复杂度（空间复杂度为 $O(n^2)$）求出任意两点间的最短路径长度。 Floyd 算法适合稠密图，稠密图边的数量（不考虑重边和自环）最大为 $\dfrac{n\times(n-1)}{2}$。 ### 算法步骤 1. 状态设立 >设 $dis_{i,j}$ 表示二元组 $(i,j)$ 的最短路径长度。 2. 初始化 >创建一个二维数组 $dis$，并将其初始化为图的邻接矩阵。即如果二元组 $(i,j)$ 存在直接边，则 $dis_{i,j}$ 等于边的权值；否则，$dis_{i,j}$ 需要设置为无穷大。 3. 状态转移 >假设 $k$ 为二元组 $(i,j)$ 的最短路径上的一个点。 则状态转移为：$dis_{i,j}=\min(dis_{i,j},dis_{i,k}+dis_{k,j})$。 时间复杂度和空间复杂度允许的情况下才能用，否则直接挂掉（小优化+O2+关闭同步流 $n$ 差不多可以到 $1000$）。 假设有一个有向图： |点|$A$|$B$|$C$|$D$| |:-:|:-:|:-:|:-:|:-:| |$A$|$0$|$3$|$∞$|$7$| |$B$|$8$|$0$|$2$|$∞$| |$C$|$5$|$∞$|$0$|$1$| |$D$|$2$|$∞$|$∞$|$0$| 在运行了 Floyd 算法之后，矩阵变为： |点|$A$|$B$|$C$|$D$| |:-:|:-:|:-:|:-:|:-:| |$A$|$0$|$3$|$5$|$6$| |$B$|$5$|$0$|$2$|$3$| |$C$|$3$|$6$|$0$|$1$| |$D$|$2$|$5$|$7$|$0$| 然后呢？ ~~完了啊。~~ 开个玩笑。 Q：如何用 Floyd 判断经过的点？ A：这个很好办，如果 $dis_{s,k}+dis_{k,t}=dis_{s,t}$（$s$ 为起点，$t$ 为终点，$k$ 为中转点）。 但是一定要记得 **$dis_{i,j}(i\ne j)$ 要初始化为无穷大！！！** 如果你不这么做的话，就会被这组数据卡掉： Input： ```cpp 6 6 1 2 3 1 3 7 1 4 5 1 5 3 1 6 2 1 7 3 ``` Output： ```cpp 1 7 ``` Wrong Output： ```cpp 1 2 5 7 ``` 不初始化的话，判断时可能会把很多无关内容加进来（甚至有可能到不了终点），但是你的 $dis=0$，所以程序会错误地将这些点当成答案…… Q：如何用 Floyd 判断有向图中的负环？ A：先运行一遍 Floyd，根据负环的概念，如果 $dis_{i,i}<0$，说明存在负环（没有负环的图中 $dis_{i,i}$ 只可能等于 $0$）。 ## Johnson 算法 前面说到，Dijkstra 算法是不能求解有负权边的图的。但是假如有一道题，需要你求解所有点对之间的最短路径。但是用 SPFA 会被卡，Floyd 会超时，又有负权边怎么办？ 比如说洛谷 [P5905](https://www.luogu.com.cn/problem/P5905) 就是一个最好的例子。 于是便有了 Johnson 全源最短路径算法。 我们建立一个超级源点 $0$，向其他 $n$ 个点连接一条权值为 $0$ 的边。 接下来从 $0$ 开始跑一遍 SPFA（不是说会被卡吗），记作 $h$。 然后将边权重新设定。 假设有一条从 $u$ 到 $v$ 的边，边权为 $w(u,v)$，那么现在的边权为 $w(u,v)+h_u-h_v$。 最后跑 $n$ 遍 Dijkstra 就好了，注意对于每一个最短路径 $dis_{i,j}$，最短路径会多出 $h_i-h_j$，减去就行了。 Q：为什么只会多出 $h_i-h_j$ 呢？ A：假设我们有一条从 $1$ 到 $4$ 的最短路： $$ w(1,2)+h_1-h_2+w(2,3)+h_2-h_3+w(3,4)+h_3-h_4 $$ 化简式子得到： $$ w(1,2)+w(2,3)+w(3,4)+h_1-h_4 $$ 通过计算发现，最后的式子仅需要 $h_{s}-h_{t}$（$s$ 代表起点，$t$ 代表终点）。 ## 最小生成树 ### 定义 对于一张图，我们从一个图中挑出 $n-1$ 边生成一棵树，使得该树的边权之和最小。 **最小生成树可能不唯一，但其边的权重之和一定是唯一的。** ### 实现（Kruskal 算法） Kruskal 算法利用并查集生成最小生成树（有点贪心的思想）。 首先我们将边权从小到大排序（保证权值和最小），然后选择边，如果这条边的两端不在同一个连通块，那么选择这条边，直到选择出了 $n-1$（大于 $n-1$ 条边必然有环）条边。 ## 最短路径树 ### 定义 最短路径树（英文：Shortest Path Tree）），简称 SPT，就是从一张连通图中，选择一些边，满足从根节点到任意点的路径都为原图中根到任意点的最短路径的树（差不多就是最短路径吧）。 ### 关于最小生成树和最短路径树的区别 好像是许多 OIer 的误区？ 1. 定义不同 最小生成树的定义是对于一个连通的无向图，最小生成树是一个包含图中所有顶点的无环子图，并且该子图的边的权重之和最小。最短路径树的定义是对于一个带权图，最短路径树是一个根节点到图中所有其他节点的最短路径的集合。 2. 性质不同 - 最小生成树： 1. 无环。 2. 生成树的边数为 $n-1$。 - 最短路径树： 1. 有向。 3. 可以有负权边（但不能有负环）。 P.S.：最短路径树其实挺好用的，尤其是在需要求出最短路径的场景中。 ## 同余最短路 同余最短路是一种通过同余把状态分类，再通过建图跑最短路解决问题的算法，可以高效率解决一些特定的问题。 ### 原理 选择一个模数 $p$（通常我们会选取最小的模数），余数为 $i$ 的整数构成一个同余类，我们记为 $dis_i$，表示通过给定的整数拼凑出的，模 $m$ 余 $i$ 的最小整数。 将每个同余类看作图中的一个节点，根据给定的整数之间的关系建边。若给定整数 $a$ 和 $b$，对于节点 $i$，可以向节点 $(i+a) \bmod p$ 和节点 $(i+b) \bmod p$ 分别建一条边，边权分别为 $a$ 和 $b$。 然后跑一遍最短路（通常从 $0$ 开始），求出从起点到其他所有同余类的最短路径长度。 Q：不是说 SPFA“死了”吗？为什么在同余最短路中，还是有许多人用 SPFA 呢？ A：因为同余最短路的图的结构是一定的，不会出现像菊花图，网格图之类的特殊图，而且有的题目中 SPFA 运行速度比 Dijkstra 运行速度还要快。所以在一定程度上，SPFA 又“复活”了。 ## 关于建边 说真的，其实最短路算法不难，建边是最难的。 比如说 [P1983](https://www.luogu.com.cn/problem/P1983)，你可以轻松（真的轻松吗）看出这是拓扑排序，但是难以想出怎么连边（有可能是我太菜了），其实只需要没经过的点向所有进过的点连一条边就好了。 结论是挺简单的，但是很难想出来，这就是它的难点。 掌握了如何建边最短路差不多就学好了。