Floyd
2026-01-31
简介
Floyd 是一个最短路算法,本质是 DP。
实现
令 fk,i,j 表示所有从 i 出发,最终到达 j,路径上所有点编号不大于 k 的最短路径长度。
关于转移,很明显可以根据 k 来划分,若不经过节点 k,则 fk,i,j=fk−1,i,j;若经过节点 k,则 fk,i,j=min{fk−1,i,k+fk−1,k,j}
但是这种做法的空间复杂度是 O(n3),并不能满足我们的要求,考虑去掉 k 这一维,空间复杂度变为 O(n2)(证明略)。
典型例题
Acwing 1125. 牛的旅行
题目传送门
这道题给我们一个无向图,有多个连通块,每个连通块的直径定义为最远的两个点的最短距离。
然后,我们需要在两个连通块间加一条边,使加完后所有连通块直径最大值最小。
这个时候,直径的最大值有两种情况:
- 取在某个连通块上
容易发现,我们加边的操作一定不会让最大值变小,即答案不小于未加边最大直径。 - 取在新的连通块上
这种时候很明显要算直径,但是加边操作并不影响原本的结构,也就是说我们可以提前处理出每个点的最远距离(直径),只需要拼接一下就可以了。
这样做的复杂度是 O(n3),可以通过本题。
传递闭包
在交际网络中,给定若干个元素和若干对二元关系,且关系具有传递性。“通过传递性推导得出尽量多的元素之间的关系”的问题称为传递闭包。
通俗的讲,传递闭包就是指通过 a 与 b 的关系,b 与 c 的关系,得出 a 与 c 的关系。
这类题目的做法一般有一个矩阵 d,若 di,j=1 则代表 i 与 j 有关系,否则没关系。 343. 排序
Acwing 343. 排序
题目传送门
Floyd 可以在 O(n3) 内完成传递闭包,根据传递闭包的思想,我们令 di,j=0 表示 i 和 j 关系未知;di,j=1 表示 i>j。
容易发现,出现矛盾的只能是 di,i=1 时,进行判断即可。
求最小环
固定经过边数
Acwing 345. 牛站
题目传送门
由于最多只有 100 条边,所以最多有 200 个节点,考虑 Floyd。
对于 Floyd 而言,它的 fk,i,j 表示从 i 到 j,仅经过编号为 1∼k 的节点的最短路径长度。
很明显,这不能满足边数的限制,所以我们将状态更改为 fa+b,i,j 表示从 i 到 j,经过 a+b 条边的最短路径长度,转移很明显是 fa+b,i,j=fa,i,k+fk,j (1≤k≤n)。
但是,如果直接做复杂度是 O(MN3)(这里的 N 是点数),所以考虑优化。
目前的复杂度瓶颈是每增加一条边都要重新枚举,所以考虑倍增,可以使用快速幂的思想,将 k 进行二进制分解然后跑魔改后的 Floyd。
时间复杂度 O(N3logM)。
