稀疏图上更快的单源最短路算法

Moeebius · 2025-01-28 17:26:47 · 个人记录

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 的堆，可能复杂度不太对。看的时候自行脑补一下就好了。