你真的懂 Floyd 吗
SUNCHAOYI
·
·
算法·理论
-
Floyd 求最短路，时间复杂度 O(n^3)，空间复杂度 O(n^2)。
for (int k = 1;k <= n;++k)
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j) dis[i][j] = min (dis[i][j],dis[i][k] + dis[k][j]);
-
【Q1】该算法的正确性？
算法基于动态规划。设 f_{k,i,j} 表示只能借助于 1,2,\cdots,k 点时，i \to j 的最短路径。那么根据是否经过 k 点，可以列出状态转移方程：
f_{k,i,j} = \min (f_{k - 1,i,j},f_{k - 1,i,k} + f_{k - 1,k,j})
很好理解，后者相当于以 k 作为中转站，即 i \to k \to j 的转移。那么当处理询问 u,v 时，f_{n,u,v} 即为所求。
可以发现 f_{k,i,j} 只对 f_{k - 1,i',j'} 产生依赖，不难想到可以滚动数组优化。那么，Floyd 最终直接删去那一维，这样做不会出错吗？
现在我们去掉第一维，只要保证在转移时方程右侧的 f_{i,j},f_{i,k},f_{k,j} 都是未被覆盖过的即可。当最外层为第 k 次循环时，显然 f_{i,j} 还未被覆盖。对于 f_{i,k},f_{k,j}，按照之前的三维转移方程，可以得到 f_{k,i,k} = \min (f_{k - 1,i,k},f_{k - 1,i,k} + f_{k - 1,k,k}) = f_{k - 1,i,k}，f_{k,j} 同理。因此我们证明了空间优化的该算法的正确性。
与此同时，从动态规划的角度出发，“为什么 k 循环需要放在最外层？”也就很好理解了。
【Q2】若每次修改一条边的权值，有必要重新完整的去做一遍 Floyd 算法吗？
答案是否定的，只需要 O(n^2) 即可实现局部更新。设 (u,v) 的权值更新为 w(u,v)（无向图），则可得到转移方程：
f_{i,j} = \min (f_{i,j},\min (f_{i,u} + w(u,v) + f_{v,j},f_{i,v} + w(v,u) + f_{u,j}))
例题：
Another Exercise on Graphs (easy version)
Another Exercise on Graphs (hard version)
解析：
根据边权排序，然后答案显然就是某一条边的值。当枚举到第 i 条边的时候，比其小的边均置为 0，否则为 1。若 i \to j 的最短路是 w_i，那么第 i + 1 大的便是这条边。
进一步的，\texttt{E2} 的 m 很大，可是我们会发现有效的更新只有 n - 1 次，因为之后 (i,j) 的最短路已经为 0，不会再发生变化，并查集维护即可。
【Q3】变式 1 【模板】传递闭包
简单来说，如果原关系图上有 i 到 j 的路径，则其传递闭包的关系图上就应有从 i 到 j 的边，均用 0/1 表示。因此枚举中转点 k，若 (i,k) 与 (k,j) 均有连边，则可将 (i,j) 连边。写成表达式，就是：
f_{i,j} = \max (f_{i,j},\min (f_{i,k},f_{k,j}))
【Q4】变式 2 [USACO07NOV] Cow Relays G 本质同 Walk
设 A 中是经过 x 条边的最短路，B 中是经过 y 条边的最短路。通过以下转移后，可以发现 C 中是经过 x + y 条边的最短路：
C_{i,j} = \min ({C_{i,j}},A_{i,k} + B_{k,j})
这样我们的转移就变得简单，重载后直接通过矩阵快速幂即可解决问题。
进一步的变式 [SCOI2009] 迷路，衡量距离。拆点与 bitset 的优化，时间复杂度 O(\frac{n^3}{64} \log k)。具体来说，对于一个点，拆成 v_1 \sim v_{10}，然后 u \to v 一条边为 w 的边，然后 v_i \to v_{i - 1} 进行连边，于是可以变为 u \to v_w。