全源最短路 (APSP) 近似。有两种近似
- stretch \(k\). \(\delta(u, v) \leq d(u, v) \leq k\cdot \delta(u, v)\).
- surplus \(t\). \(\delta(u, v) \leq d(u, v) \leq \delta(u, v) + t\).
其中，\(\delta(u, v)\) 表示 \(u, v\) 间真实的最短路长度。
先来考虑无权图上的 surplus \(2\) 近似。\(2\) 代表着我们可以选择最短路上的某个邻居作为转移点。
一个想法是，将一个 \(O(n^2)\) 条边的图中较密集的部分删去。得到一个 \(O(n^{\frac 32})\) 条边的图。
考虑将图上一些点设为关键点，使得所有度数大的点与至少一个关键点相连，用这些关键点转移这些度数大的点，而将度数大的点之间的边删去。
考虑图上每个点有 \(\frac 1k\) 的概率被选为关键点，则度数为 \(d\) 的点有 \(1 - \left(1 - \frac 1k\right)^d\) 的概率与一个关键点相邻。当 \(k = \frac d{c\log n}\) 时，\(1 - \left(1 - \frac 1k \right)^d \geq 1 - \frac 1{n^c}\)，因此
定理 1 给定度数 \(d\)，可以找到一个大小为 \(\tilde O(\frac nd)\) 的集合 \(D\)，使得高概率所有度数 \(\geq d\) 的点都与至少一个 \(D\) 中的点相邻。
其中 \(\tilde O\) 表示 \(O\) 忽略 \(\log\)。
于是我们可以平衡二者。
|
算法 1 （无权图上的 surplus \(2\) 近似 I [Aingworth-Chekuri-Indyk-Motwani '96]） 对图 \((V, E)\)，令
对 \(u \in D_1, v \in V\)，用 BFS 计算出所有 \(\delta(u, v)\)。时间复杂度 \(O(m |D_1|) = \tilde O(\frac{nm}d)\)。令 \(\delta(D_1 \times V)\) 表示 \(\{(u, v, \delta(u, v))\}\)。 对 \((V, E_2 \cup \delta(D_1 \times V))\) 跑 Dijkstra。时间复杂度 \(O(n(|E_2| + n|D_1|)) = O(n^2d)\)。 考虑将 Dijkstra 的结果作为答案。
因此这是一个 surplus \(2\) 近似。 时间复杂度为 \(\tilde O\left(n^2d + \frac{nm}d\right)\)，令 \(d = n^{-\frac 12}m^{\frac 12}\)，最终时间复杂度为 \(\tilde O(n^{\frac 32}m^{\frac 12})\)，一般图 \(m = O(n^2)\) 时为 \(\tilde O(n^{\frac 52})\)。 |
这个算法是可以被优化的。考虑最短路上 \(w\) 的一个相邻的关键点 \(w'\)，\(u\to w\to w' \to w \to v\) 也是一个合法的 surplus \(2\) 近似。因此算法 1 的浪费之处在于用 BFS 求出了所有的 \(\delta(D_1 \times V)\)。我们并不需要 \(D_1\) 到 \(V\) 的一般意义上的最短路，而可以强制所有的近似都采取这样的策略，那就只需要对最短路上的边和 \(w\) 与 \(w'\) 的边跑 BFS 即可。但是我们无法提前知道要保留的边是哪些。
一个折中是先进行一次对度数大小的分治，将度数小的用 Dijkstra 求出精确解，度数大的再进行一次分治，度数更大的用 BFS，度数处于中间的用度数小的导出的边跑 BFS，再跑 Dijkstra。
|
算法 2 （无权图上的 surplus \(2\) 近似 II [Dor-Halperin-Zwick '96]） 对图 \((V, E)\)，令
用 BFS 计算 \(\delta(D_2 \times V)\)。时间复杂度 \(O(m |D_2|) = \tilde O\left(\frac{n^3}{d_2}\right)\)。 用 BFS 在生成子图 \((V, E_2)\) 上计算 \(\delta'(D_1 \times V)\)。时间复杂度 \(O(|E_2||D_1|) = \tilde O\left(\frac{n^2d_2}{d_1}\right)\)。 对 \(u \in V\)，在 \((V, E_1 \cup \delta(D_2 \times V) \cup \delta'(\{u\} \times D_1) \cup E^*)\) 上跑 Dijkstra。时间复杂度 \(\tilde O\left(n\left(nd_1 + \frac {n^2}{d_2} + \frac n{d_1} + n\right)\right) = \tilde O\left(n^2d_1 + \frac {n^3}{d_2}\right)\)。 考虑将 Dijkstra 的结果作为答案。
因此这是一个 surplus \(2\) 近似。 时间复杂度为 \(\tilde O\left(\frac{n^2d_2}{d_1} + n^2d_1 + \frac{n^3}{d_2}\right) = \tilde O\left(n^2\left(d_1 + \frac {d_2}{d_1} + \frac n{d_2}\right)\right)\)，后三者乘积为 \(n\)。令 \(d_1 = n^{\frac 13}, d_2 = n^{\frac 23}\)，最终时间复杂度为 \(\tilde O(n^{\frac 73})\)。 |
注意在第四种情况中只有当我们选了最后一个这样的 \(w\) 才可以让处理 \(d(u, v)\) 时仅包含 \(\delta'(\{u\} \times D_1)\)，否则需要 \(\delta'(\{u, v\} \times D_1)\)，由于要对所有 \(v\) 求，因此只能一股脑把 \(\delta'(D_1 \times V)\) 全部加进去，但这样将失去任何复杂度优势。
这个算法使用了两个指标，将度数分为三层。立刻产生的想法便是可不可以通过分更多层来得到更优秀的复杂度，比如 \(O(n^{2 + \frac 1k})\)。答案是否定的。原因仍然是上面的 \(\delta'(\{u\} \times D_1)\)，能只加入以 \(u\) 为起点的 \(\delta'\) 的前提是，\(w \to v\) 的所有边 \(\in E_1\)，即 \(d_2\) 的下一层，这样才能在选取最后一个满足条件的点时 \(v\) 这一侧可以不在乎。如果有超过三层，每次求出 \(\delta_k(D_k \times V)\)，在 Dijkstra 中能够只加入 \(\delta_k(\{u\} \times D_k)\) 的前提，就不是加入 \(|E_1| = O(nd_1)\) 条边，而是 \(|E_{k-1}| = O(nd_{k-1})\) 条边了。因此这个做法下分更多层没有意义。
我们也可以把算法 2 看作仅考虑一个待定值 \(d_2\)，将 \(G' = (V, E_2)\) 直接应用算法 1，这样的复杂度为 \(\tilde O\left(\frac{n^3}{d_2}+n^{\frac 32}(nd_2)^{\frac 12}\right)\)，令 \(d_2 = n^{\frac 23}\)，也可以得到 \(\tilde O(n^{\frac 73})\) 的结果。
我们仍有一个外在的优化，即使用更快速的矩乘算法。注意到在 Dijkstra 中 \(\delta(D_k \times V)\) 的贡献和任何其他部分独立，我们需要的只是 \(\min_w\{\delta(u, w) + \delta(w, v)\}\)，如果我们能加速这一过程，那么便能加速复杂度。
更进一步地，上文 “一股脑把 \(\delta'(D_2 \times V)\) 全部加进去将失去任何复杂度优势” 以及 “分更多层没有意义” 都会被 invalidate。这会是一个很有趣的事情，我们可以看到基本算法的复杂度关系是如何塑造最终算法的形态的。
将 \(\delta(V \times D_1)\) 视作矩阵，则我们需要求出 \(\delta(V \times D_1) \star \delta(D_1 \times V)\)，其中 \(\star\) 表示 \((\min, +)\) 矩阵乘法。如果我们将节点序列按照图的任意一棵生成树的欧拉序排列（此时一个点会出现多次），则 \(\delta(D_1 \times V)\) 的上下相邻两个元素的差不超过 \(1\)。对一般的 \((\min, +)\) 矩阵乘，没有 \(O(n^{3 - \Omega(1)})\) 的做法，但是对于拥有这样特殊性质的矩阵乘（其中一个矩阵为 Row/Column Bounded-difference），有 \(\tilde O(n^{(2 + r + \omega(r))/2})\) 的做法，其中 \(\omega(r)\) 表示 \(n \times n^r\) 矩阵和 \(n^r \times n\) 矩阵做正常矩阵乘法的指数 [Chi-Duan-Xie-Zhang '22]。
|
算法 3 （无权图上的 surplus \(2\) 近似 III [Deng-Kirkpatrick-Rong-V. Williams-Zhong '22]） 对图 \((V, E)\)，令
用 BFS 在 \((V, E_i \cup E^*)\) 上计算 \(\delta_i(D_{i-1} \times V)\)，\(1 \leq i \leq k\)，时间复杂度为 \(\tilde O(\frac{n^2d_i}{d_{i-1}})\)。 对 \((V, E_0)\) 应用算法 1 得到 \(d'(u, v)\)。时间复杂度 \(O\left(n^2d_0^{\frac 12}\right)\)。 求出 \(\min\limits_{\substack{w' \in D_i \\ 1 \leq i \leq k}}\{\delta_i(u, w') + \delta_i(w', v)\}\)，假设 \(d\) 的选取足够分散，使得复杂度被 \(D_0\) dominate，为 \(\tilde O(n^{(2+(1 - \log_n d_0)+\omega(1 - \log_n d_0))/2})\)。 考虑将 \(d(u, v) = \min\left(d'(u, v), \min\limits_{\substack{w' \in D_i \\ 1 \leq i \leq k}}\{\delta_i(u, w') + \delta_i(w', v)\}\right)\) 作为答案。 使用类似上文的推导可知这是一个 surplus \(2\) 近似。 时间复杂度为 \(\tilde O\left(n^2\left(d_0^{\frac 12} + \frac{d_1}{d_0} + \frac{d_2}{d_1} + \ldots + \frac{d_{k-1}}{d_{k-2}} + \frac n{d_{k-1}}\right) + n^{(2+\log_n d_0+\omega(\log_n d_0))/2}\right)\)，首先可知 \(\frac{d_i}{d_{i-1}}\) 都相等，令他们均为 \(2\)，则 \(k = O(\log n)\)，被归档到 \(\tilde O\) 里。剩下的便是解方程，令 \(d_0 = n^{1 - r}\)，则方程为 \(\frac 52 - \frac 12 r = (2 + r + \omega(r))/2\)，即 \(2r + \omega(r) = 3\)，\(\omega(r)\) 是一个很复杂的函数，查表可以估计出 \(r \approx 0.427\)，最终复杂度 \(\tilde O(n^{2.2867})\)。 |
一个额外的事情是，我们可以将定理 1 去随机化。考虑对一个点 \(v\)，如果将其作为关键点，则 \(v\) 和 \(v\) 的邻居都被覆盖了。我们总是从没有被覆盖的点中再考虑一个作为关键点，也即每次将 \(v\) 和 \(v\) 的邻居删去，考虑剩下的图。如果再限制从度数大的开始删，那么当删去 \(B\) 个点的时候，如果度数第 \(B\) 大的值为 \(d - 1\)，则 \(\geq Bd\) 个点被删去了，剩下的度数均 \(< d\)，因此 \(n \geq Bd, B \leq \frac nd\)。因此可以找到一个大小 \(\leq \frac nd\) 的集合 \(D\)，使得所有度数 \(\geq d\) 的点都与至少一个 \(D\) 中的点相邻。此时甚至不需要 \(\log\)，以上算法的所有 \(\tilde O\) 可以改为 \(O\)。
对于有向图，由于上述算法均有 \(w\to w'\to w\) 的情节，无法再适用。对于有权图，相邻并不意味着距离相近，因此 surplus 并不合理，现在尝试考虑 stretch。
先来考虑怎么寻找一个点 \(s\) 前 \(b\) 相近的点。如果直接使用 Dijkstra，复杂度是 \(\tilde O(nb)\) 的，不过我们可以限制 Dijkstra 的运行轮数与队列长度做到 \(\tilde O(b^2)\)。
一个最朴素的想法是这样的，我们还是沿用寻找关键点 \(w\)，用 \(d(u, v) = \delta(u, w) + \delta(w, v)\) 来近似 \(\delta(u, v)\) 的方法。此时若有 \(\delta(u, w) \leq \delta(u, v)\)，则 \(\delta(w, v) \leq \delta(w, u) + \delta(u, v) \leq 2\delta(u, v), d(u, v) = \delta(u, w) + \delta(w, v) \leq 3\delta(u, v)\)，因此得到一个很粗糙的上界 stretch \(3\)。
|
算法 4 （带权图上的 stretch \(3\) 近似） 对图 \((V, E)\)，令
对每个 \(D\) 跑完整的 Dijkstra，得到 \(\delta(D \times V)\)。 对于 \(u \in D \vee v \in D \vee v \in \mathrm{ball}(u)\)，\(d(u, v) = \delta(u, v)\)。 否则，考虑 \(w \in \mathrm{ball}(u) \cap D\)，\(d(u, v) = \delta(u, w) + \delta(w, v)\)。 这是一个 stretch \(3\) 近似。 时间复杂度为 \(\tilde O\left(nb^2 + \frac{n^3}b\right)\)，令 \(b = n^{\frac 23}\)，最终时间复杂度为 \(\tilde O(n^{\frac 73})\)。 |
这是一个广为人知 (folklore) 的算法。更优秀地，stretch \(2\) 有 \(\tilde O(n^{\frac 32}m^{\frac 12})\) 的做法，stretch \(\frac 73\) 有 \(\tilde O(n^{\frac 73})\) 的做法，stretch \(3\) 有 \(\tilde O(n^2)\) 的做法。[Cohen-Zwick '97]
如果考虑空间复杂度的优化，我们所做的便是把规模 \(n \times n\) 的最短路表 \(\delta(V \times V)\) 化简为一个空间更小的数据结构，使其能快速查询两点间的（近似）最短路。在上面的算法中为 \(O(n^{\frac 53})\) 空间 \(-\ O(1)\) 查询，如果不考虑时间复杂度的最优，令 \(b = n^{\frac 12}\)，能做到 \(O(n^{\frac 32}) - O(1)\)。对 stretch \(2k - 1\) 有 \(O(kn^{1 + \frac 1k}) - O(k)\) 的做法 [Thorup, Zwick '01]。
如果我们在无权图上允许 stretch，那非常轻松地我们可以给出一个与输入同阶的，\(\tilde O(n^2)\) 的算法。优化点在于我们不用像算法 3 那样计算出 \(\min\limits_{\substack{w' \in D_i \\ 1 \leq i \leq k}}\{\delta_i(u, w') + \delta_i(w', v)\}\)，而实际上只需要用那个离 \(u\) 最近的关键点和那个离 \(v\) 最近的关键点作为转移点，因为两者恰好没有一半的最短路长度。
|
算法 5 （无权图上的 \((2, 1)\) 近似） 对图 \((V, E)\)，令
用 BFS 在 \((V, E_i \cup E^*)\) 上计算 \(\delta_i(D_{i-1} \times V)\)，\(1 \leq i \leq k\)，时间复杂度为 \(\tilde O(\frac{n^2d_i}{d_{i-1}})\)。 考虑将 \(d(u, v) = \min\limits_{1 \leq i \leq k}\{\delta_i(u, u'_i) + \delta_i(u'_i, v), \delta_i(u, v'_i) + \delta_i(v'_i, v)\}\) 作为答案，其中 \(u'_i = \operatorname{argmin}\limits_{w \in D_i} \delta_i(u, w), v'_i = \operatorname{argmin}\limits_{w \in D_i} \delta_i(w, v)\)。
因此这是一个 \((2, 1)\) 近似。 时间复杂度为 \(\tilde O(n^2)\)。 |
对于 \((2, 0)\) 近似，有
-
\(\tilde O(n^{2.032})\) [Dory-Forster-Kirkpatrick-Nazari-V. Williams-Vos '23]。
-
\(\tilde O(n^{2.25})\) 的组合算法 [Roditty 2023]。