TL;DR：这是一个求解无向图（非负实数边权）上单源最短路问题，期望复杂度为 $O(n \sqrt{\log n \log \log n})$ 的非确定性做法。（以下讨论均默认 $n,m$ 同阶）

做法来源：WC 2025 讲课。原论文见 link。

回忆 dijkstra 为什么无法突破 $O(n \log n)$：注意到 dijkstra 中保证了答案是按照最短路长度从小到大的顺序被确定的，也就是我们做了 $\text{DO\tiny{(Distance Ordering)}}$ 而非 $\text{SSSP\tiny{(Single Source Shortest Path)}}$，并且事实上前者需要做实数排序，因此更难。

那么如何绕开排序呢？一个想法是，我们选出若干个关键点，然后把剩下的点挂在关键点上，关键点间按照最短路从小到大做，剩下的点跟着关键点更新即可。由于关键点数量是 $o(n)$，所以我们的复杂度有希望低于 $O(n \log n)$。

事实上，这一算法就是这么做的。

默认图连通，定义 $dis_{u,v}$ 为图上 $u$ 到 $v$ 的最短路径。不妨假设将 $dis$ 赋予第二关键字——路径中经过的边数，第三关键字——路径终点编号大小。不难发现这样 $dis$ 两两不同，并且 dijkstra 求出的确实可以求出符合这一定义的最短路。

设定阈值 $B$，考虑在图上令每个点以 $\frac{1}{B}$ 的概率成为关键点。定义关键点集合 $R$。接下来考虑每个非关键点 $u$：

  • 定义 $b_u$ 为离其最近的关键点；
  • 定义 $\text{Ball}_u = \{v | dis_{u,v} < dis_{u,b_u}\}$；
  • 容易发现 $\text{Ball}_u$ 的期望大小是 $O(B)$。

此外，对于关键点 $p$，定义 $\text{Bundle}_p=\{u|b_u=p\}$。

考虑如何求出 $\text{Ball}$ 和 $\text{Bundle}$。直接对每个非关键点跑 dijkstra 就好了……吗？不难发现如果来个菊花复杂度就爆了。我们只能接受每个点度数是常数的图。

所以在运行这一算法前，我们要先对图结构做一些改造。对于一个原图上度数为 $d$ 的点我们把他拆成 $d$ 个新点然后用一条链串起来。每连一条边我们就从两个点对应的新点里面选一个没用过的连起来。这样度数就对了。

好了我们现在在期望 $O(nk \log k)$ 的时间内建出来了我们要的结构。回顾我们想要的过程：

  • 定义 $d_x$ 为当前找到的起点到 $x$ 的最短路长度。
  • 使用一个堆维护所有关键点，取出目前 $d(\cdot)$ 最小的关键点 $p$，我们希望现在 $d_p = dis_{s,p}$（1）；
  • 我们接下来能顺路把 $\text{Bundle}_p$ 内所有点的最短路算对（2）。

下面是算法过程，证明有空补：

  • 只要在松弛点 $u$ 的时候顺带更新 $b_u$ 就可以满足第一个要求；
  • 对于第二个要求，我们枚举所有 $u \in \text{Bundle}_p$，枚举 $\text{Ball}_p \cup N(\text{Ball}_p)$ 内的所有点更新 $d_u$；更新完成后 $d_u=dis_{s,u}$，再用 $d_u$ 更新所有 $N(u)$ 和 $\{i \in \text{Ball}(p) | p \in N(u)\}$。

算一下复杂度，这里的复杂度是 $O(\frac{n}{B} \log \frac{n}{B}+nB)$。平衡一下就是开头那个复杂度。

代码并不是特别难写。常数还行，不过也不是特别小。空间常数很大。代码可以见 loj。

upd：没用 $O(1)$ dec-key 的堆，可能复杂度不太对。看的时候自行脑补一下就好了。

标签: graph

添加新评论