作为相关 paper 的学习笔记好了。基本但不是百分百翻译论文。

前置知识：

Dijkstra（下称 Dj），和其他一些同难度的基础算法。
至少一种线性树上并查集。不会的话可以看这个（如果会 Top Cluster 树分块，注意那个启发式合并改成裸的双优并查集也是对的）或者这个（0 基础也能看！！1）。

开始前提示：

WRM（$\omega=\Omega(\log n)$）。
线性 Dj 双向规约线性排序，这个大家还不太会，所以这个算法对 Dj 进行了一定的延展。但由于其本质上还是基于 Dj 那一套贪心思路的，我们在文章前期依然可能会用 Dj 中的相关流程来进行指代。
不保证笔者写得很顺畅，但保证一定大体能看。可能会有细节脑抽（比如把 $[v]_i$ 写成 $v[i]$），如有发现还望指出。
paper 主部分有 38 个引理 7 个伪代码，作为进度条本文会在每个引理和伪代码前面给出编号。这里由于没有 paper 在解决问题之后碎碎念的一大段所以只有 37 个引理。
$\subset$ 不取等号。
涉及数据结构 Q 堆（实现出来会被降格为平凡暴力数组所以不用太在意）。晚点可能补二叉堆版代码以及补那个单 $\alpha$ 但不需要原子堆的做法。
全文共 27k 文字分析纯干货，请放心食用。

SSSP，启动！

1. 预工作

整理一些字母：

（宏观类）$G$ 是图，$V$ 是点集，$E$ 是边集，$w$ 表示两点间边权（无边则改为权充分大），$s$ 是源，$d$ 是最终答案。
（微观类）$S$ 是当前扩展到的点集（对应到 Dj 上就是某个点出堆后更新完所有邻边这个时间状态下所有出过堆的点的集合），$D$ 是 $S$ 的时间状态下每个点暂时求出的最短路。

整理一些引理：

（引理 1）$V\backslash S$ 中 $D$ 的最小值点 $v$ 满足 $D_v=d_v$。
（引理 2）如上的 $D_v$ 在 $S$ 扩展的流程中不降。

整理一些约定：

用 $x>>i$ 表示 $\lceil\frac x{2^i}\rceil$。规定这个运算的优先级非常低。
对于一个参数为单个元素的函数 $f$，我们补充定义 $f$ 在参数为可重集时表示其中每个元素的函数值构成的集合。
定义 $\min(\varnothing)=+\infty$，同时 $\max(\varnothing)=0$。

称一个数据结构为一个“桶”，当且仅当它能在 $O(1)$ 时间内实现加入元素，删除元素和随机取出元素。一个双向链表就是一个很好的“桶”的例子。

2. 瓶颈规避

注意到我们前面说过线性 Dj 双规线性排序，所以我们要做线性必须把 Dj 的限制放宽一些。我们考虑这样一件事情，我们在扩展的流程中其实不必每次都取 $V\backslash S$ 中 $D$ 的最小值点更新，我们实际上只需要它满足这个点 $v$ 的 $D_v=d_v$ 就可以了。进一步，我们只要保证这个 $v$ 不会被再更新就可以了。我们记 $\min(D(V\backslash S))=L$，那么只要满足 $D_v\le L+\min(w)$ 就一定可行。我们考虑对这个思路进行延展，给出以下引理：

（引理 3）如果把 $V$ 划分成若干个子集 $V_1,V_2,\cdots,V_k$ 的不交并，同时不同子集间的最小边权不小于 $\delta$，那么 $\forall 1\le i\le k$，考虑 $v=\arg\min(D(V_i\backslash S))$，那么如果有 $D(v)\le L+\delta$ 成立，那么有 $D(v)=d(v)$。

这样的点不会再被点集内外的任何一个点更新了。

我们考虑把它的条件稍微改强一点：

（引理 3·改）如果把 $V$ 划分成若干个子集 $V_1,V_2,\cdots,V_k$ 的不交并，同时不同子集间的最小边权不小于 $\delta=2^\alpha$，那么 $\forall 1\le i\le k$，考虑 $v=\arg\min(D(V_i\backslash S))$，那么如果有 $D(v)>>\alpha\le L>>\alpha$ 成立，那么有 $D(v)=d(v)$。

我们考虑对每个 $\min(D(V_i\backslash S))>>\alpha$ 开桶。我们发现，$\min(D(V_i\backslash S))>>\alpha\le L>>\alpha$ 当且仅当 $i$ 在最小的非空桶中。我们定义 $ix$ 为这样桶的下标。注意到最小桶内 $D$ 的不降性，$ix$ 将同样是不降的。我们考虑计算一下桶的数量，会发现除了下标为 $+\infty$ 的桶以外其余所有下标都在 $0$ 及以上，$\Delta=(\sum w(E))>>\alpha$ 及以下。换句话说我们其实只有这些下标有桶：$0,1,2,cdots,\Delta-1,\Delta,+\infty$。

来熟悉熟悉定义，用现在已知的结论盘个简陋的算法出来（由于笔者 $\LaTeX$ 水平低下，这里只能用中文了）：

（伪代码 1）

（事先划分好点的子集并计算 $\alpha$ 和 $\Delta$ 等。）

初始化 $S$ 为只包含源，并用它初始化 $D$。
用初始化好的 $D$ 计算出每个 $\min(D(V_i\backslash S))>>\alpha$ 并塞进桶里。
令 $ix$ 从 $0$ 到 $\Delta$ 遍历，对于每个 $ix$ 循环直至当前桶为空：
1. 从 $B_{ix}$ 中任意取出 $i$，并取出 $v=\arg\min(D(V_i\backslash S))$。
2. 用 $v$ 更新出边，如果出边对应集合 $j$ 的 $\min(D(V_j\backslash S))>>\alpha$ 因此变小，将 $j$ 从原来的桶中删去并加入新的桶中。
3. 将 $v$ 加入 $S$ 中。如果 $\min(D(V_i\backslash S))>>\alpha$ 因此变大，将 $i$ 从原来的桶中删去并加入新的桶中。

（我们来举个例子感性理解一下这个东西。如果 $k=1$，那么 $ix$ 一定是追着 $1$ 的所在桶跑的，取出来的每个 $i$ 也一定只能是 $i$，如此一来我们不再关心桶的维护，会发现这个就是 Dj）。

我们会意识到，除去中间“如果……因此变大，将……从原来的桶中删去并加入新的桶中”这一部分，其他部分的复杂度是 $O(m+\Delta)$ 的。我们在后续的部分会指出，前者靠递归做，后者可以通过控制一个比较大的 $\delta$ 来控制 $\Delta$ 的规模。

3. 联通块分级

显然，上面那个算法还很粗糙，不堪大用；短时间内我们不会再见到它，待到重逢，框架大概已经认不出来了。无论如何，让我们把视线稍微从那里挪开，来研究一点别的东西。

我们定义 $G_i=(V,\{(u,v)|(u,v)\in E\land w(u,v)\lt 2^i\})$；翻译成人话，$G$ 中只保留所有权 $\lt 2^i$ 的边构成的子图。如此一来，$G_0=(V,\varnothing)$ 且 $G_\omega=G$。$\forall 0\le i\le\omega$，将 $G_i$ 划分成若干个联通块，其中包含点 $v\in V$ 的点的联通块记作 $[v]_i$（其实是一个集合，但注意每层之间会有区分）。让我们以一个简单的引理来熟悉一下定义：

（引理 4）如果 $[u]_i\not=[v]_i$，那么 $u$ 与 $v$ 之间的距离不小于 $2^i$。

（这是因为 $u$ 到 $v$ 的所有路径都必定会经过某条权不小于 $2^i$ 的边，否则与条件构成矛盾。）

很显然，如果两个点在 $G_i$ 中联通，那么它们在 $G_{i+1}$ 中也是联通的。进一步，每个 $G_{i+1}$ 中的每个联通块都是由 $G_i$ 中的若干联通块以一些边权在 $[2^i,2^{i+1})$ 间的边联结起来的，这构成了一个树形结构。我们把构成 $G_{i+1}$ 中每个联通块的 $G_i$ 中联通块称为这个联通块的儿子。可以看到，$[v]_i$ 一定是 $[v]_{i+1}$ 的儿子，且遍历联通块内每个 $v$ 后 $[v]_{i+1}$ 只有这些儿子（去重）。

让我们考虑往主线靠拢。定义 $[v]_i^-=[v]_i\backslash S$（不一定仍是联通块）。我们定义 $[v]_i$ 是 $[v]_{i+1}$ 的“小儿子”，当且仅当 $\min(D([v]_i^-))>>i=\min(D([v]_{i+1}^-))>>i$。我们称呼 $[v]_i$ 是“极小孙”，当且仅当它满足以下两条：

$[v]_i^-\not=\varnothing$；
$\forall i\le j\lt\omega$，$[v]_j$ 是 $[v]_{j+1}$ 的小儿子。

好的那么又到了喜闻乐见的熟悉定义环节：

（引理 5）如果 $v\in V\backslash S$ 且 $[v]_i$ 是极小孙，那么 $\forall i\le j\le\omega$，$\min(D([v]_i^-))>>j-1=\min(D([v]_j^-))>>j-1$。

我们再次重申位移运算符的优先级很低。我们考虑 $\forall i\le k\lt j$，那么 $\min(D([v]_k^-))>>k=\min(D([v]_{k+1}^-))>>k$（根据极小孙和小儿子定义），由于 $k\le j-1$，有 $\min(D([v]_k^-))>>j-1=\min(D([v]_{k+1}^-))>>j-1$，随后不再赘述。
（引理 6）如果 $v\in V\backslash S$ 且存在一条从 $s$ 到 $v$ 的最短路满足其上第一个在 $S$ 以外的点 $u$ 在 $[v]_i$ 中，则有 $d(v)\ge\min(D([v]_i^-))$。

在 $s$ 到 $v$ 的最短路上，$s$ 到 $u$ 的路径作为其中的一部分也一定是 $s$ 到 $u$ 的最短路。由于 $D(u)$ 已经维护出了除了终点外所有点都在 $S$ 中的最短路且 $s$ 到 $u$ 的最短路确实是这个形式，我们有 $D(u)=d(u)$ 成立。同时我们注意到 $u\in [v]_i^-$，那么有 $d(v)\ge d(u)=D(u)\ge\min(D([v]_i^-))$成立。
（引理 7）如果 $v\in V\backslash S$ 且 $[v]_{i+1}$ 是极小孙，且不存在一条从 $s$ 到 $v$ 的最短路满足其上第一个在 $S$ 以外的点 $u$ 在 $[v]_i$ 中，那么有 $d(v)>>i\gt\min(D([v]_{i+1}^-))>>i$。

$s$ 和 $v$ 不联通时显然成立。否则拎一条最短路出来满足 $u$ 在 $[v]_k$ 中且使得 $k$ 最小化，则显然有 $k\gt i$。于是我们得到 $[v]_{i+1}^-\subseteq[v]_k^-$，进而 $d(u)=D(u)\ge\min(D([v]_k^-))\ge\min(D([v]_{i+1}^-))$。根据引理 4，有 $d(v)\ge d(u)+2^i$，进而有 $d(v)>>i\gt\min(D([v]_{i+1}^-))>>i$ 成立。
（引理 8）如果 $v\in V\backslash S$ 且 $[v]_i$ 是极小孙，那么 $\min(D([v]_i^-))=\min(d([v]_i^-))$。

左式不小于右式显然成立。我们考虑 $v$ 在联通块内的任意性，考虑只需要证明 $d(v)\ge\min(D([v]_i^-))$。由于 $[v]_i$ 是极小孙，引理 6 和引理 7 的条件总有一个成立，其中前者结论与本命题一致。对于后者，$[v]_i$ 是极小孙推出 $[v]_i$ 是 $[v]_{i+1}$ 的小儿子，根据其定义有 $\min(D([v]_i))>>i=\min(D([v]_{i+1}))>>i$，那么 $d(v)>>i\gt\min(D([v]_{i+1}^-))>>i=\min(D([v]_i^-))>>i$，证毕。
（引理 8·改）如果 $v\in V\backslash S$ 且 $[v]_0=\{v\}$ 是极小孙，那么 $D(v)=d(v)$。

图穷匕见。

这是最核心的一条结论，可能也是引入这样一个联通块体系的主要目的——刻画一些确凿可以被扩展的节点。在文章的剩下部分，对于每次扩展到的节点，我们将保证 $[v]_0$ 是极小孙。

让我们继续看看其他的一些引理吧。

（引理 9）如果 $v\in V\backslash S$ 且 $[v]_i$ 不是极小孙但 $[v]_{i+1}$ 是极小孙，那么 $\min(d([v]_i^-))>>i\gt\min(D([v]_{i+1}^-))>>i$。

类似引理 8，分类引理 6 和引理 7 谁成立决定使用 $[v]_i$ 作为非小儿子的性质再推一步或者直接用前面的结论。
（引理 10）$\forall v\in V\land0\le i\le\omega$，有 $\max(d([v]_i\cap S))>>i-1\le\min(d([v]_i^-))>>i-1$。

初始时左式为 $0$，一定成立。考虑在 $S$ 扩展的过程。当我们选出 $u\in[v]_i$ 进行扩展，根据我们先前的约定，一定有 $[u]_0$ 是极小孙成立，那么有 $d(u)>>i-1=\min(d([v]_i^-))>>i-1$，等于是把 $\min(d([v]_i^-))>>i-1$ 移给左边贡献了，由于原来这个不等式成立，新移过去的一定作为左式的最大值，小于右式全体。于是每一步扩展后这个式子依然成立，证毕。

在文章接下来的部分中，我们将频繁考虑一个点被扩展前后这两个时间状态一个式子的值，我们给式子包装上 $\langle\rangle^b$ 和 $\langle\rangle^a$ 来表示这个式子在一个点被扩展前（before）和扩展后（after）的值。让我们来熟悉一下这个形式：

（引理 10·改）$\forall v\in V\land0\le i\le\omega\land i-1\le j\le\omega$，若有 $\langle\min(D([v]_i^-))>>j\rangle^b=\langle\min(d([v]_i^-))>>j\rangle^b$，则有 $\langle\min(D([v]_i^-))>>j\rangle^b\le\langle\min(D([v]_i^-))>>j\rangle^a$。把两边的 $D$ 换成 $d$ 比较，会发现左边不变而右边变小（或同样不变），而换完之后的式子和引理 10 同理。
（引理 11）若有 $\min(D([v]_i^-))>>i=\min(d([v]_i^-))>>i$，且扩展节点 $u\in V\backslash S$ 对 $\min(D([v]_i^-))>>i$ 造成了影响，则有 $u\in\langle[v]_i^-\rangle^b$；且若 $\langle[v]_i^-\rangle^a\not=\varnothing$，则影响恰为增加一。

考虑引理 10·改，得到 $\langle\min(D([v]_i^-))>>i\rangle^b\le\langle\min(D([v]_i^-))>>i\rangle^a$，进一步 $\langle\min(D([v]_i^-))>>i\rangle^b\lt\langle\min(D([v]_i^-))>>i\rangle^a$；但注意到 $D$ 值不增，一定有 $\langle[v]_i^-\rangle^a\subset\langle[v]_i^-\rangle^b$，从而 $u\in\langle[v]_i^-\rangle^b$。

对于 $\langle[v]_i^-\rangle^a\not=\varnothing$，我们考虑到 $[v]_i$ 是个联通块且至少有两个点，则一定有 $\langle[v]_i\cap S\rangle^a$ 中的一个点 $p$ 与 $\langle[v]_i^-\rangle^a$ 中的一个点 $q$ 存在一条权小于 $2^i$ 的边。根据引理 5 和引理 8，每次我们访问到的 $[v]_i$ 中的点一定可以是当时的 $\arg\min(D([v]_i^-))>>i$，同时考虑到 $\min(D([v]_i^-))>>i$ 的值不减，故 $d(p)\le d(u)$，从而 $\langle\min(D([v]_i^-))>>i\rangle^a\le D(q)>>i\lt(d(p)>>i)+1=(d(u)>>i)+1=\langle\min(D([v]_i^-))>>i\rangle^b+1$，证毕。
（引理 12）若某一时刻 $[v]_i$ 成为了极小孙，则它在 $\min(D([v]_i^-))>>i$ 变大前会一直维持这个性质，同时此时 $\min(d([v]_i^-))>>i$ 也会变大。

考虑 $[v]_i$ 是在扩展某个节点后失去极小孙的性质的。若此次扩展使 $[v]_i^-$ 变为空集，那么结论显然成立，以下考虑 $\langle[v]_i^-\rangle^a\not=\varnothing$。

我们找到最小的 $j$ 使 $[v]_{j+1}$ 是极小孙，其有儿子 $[v]_j$（非小儿子）。在扩展前，根据引理 5，我们得到有 $\langle\min(D([v]_i^-))>>j\rangle^b=\langle\min(D([v]_{j+1}^-))>>j\rangle^b$。同时，由于 $[v]_{j+1}$ 是极小孙，根据引理 8 和引理 10·改，有 $\langle\min(D([v]_{j+1}^-))>>j\rangle^b\le\langle\min(D([v]_{j+1}^-))>>j\rangle^a$。在扩展后，根据引理 9，我们得到有 $\langle\min(d([v]_j^-))>>j\rangle^a\gt\langle\min(D([v]_{j+1}^-))>>j\rangle^a$。据此，我们得到：

$$ \begin{aligned} \langle\min(D([v]_{i}^-))>>j\rangle^a\ge&\langle\min(d([v]_{i}^-))>>j\rangle^a\\ \gt&\langle\min(D([v]_{j+1}^-))>>j\rangle^a\\ \ge&\langle\min(D([v]_{j+1}^-))>>j\rangle^b\\ =&\langle\min(D([v]_i^-))>>j\rangle^b=\langle\min(d([v]_i^-))>>j\rangle^b \end{aligned} $$
（引理 13）若某一时刻 $[v]_i$ 成为了极小孙，则从此往后，$\min(D([v]_i^-))>>i=\min(d([v]_i^-))>>i$ 均成立。

在 $[v]_i$ 是为极小孙时，根据引理 8 可知不等式成立；考虑扩展一个节点 $u$ 对这个不等式的影响。如果它不再成立，根据引理 11，$u\in\langle[v]_i\rangle^b$ 且左式恰增加一，而由于 $\forall p\in V\backslash S$ 有 $D(p)\ge d(p)$，右式一定没有变化。但考虑扩展 $u$ 一定满足 $[u]_0$ 是极小孙，故而 $\langle[v]_i\rangle^b$ 是极小孙。由于不等式在 $[v]_i$ 作为极小孙时成立，可知 $\langle [v]_i\rangle^a$ 一定不是极小孙，根据引理 12 就右式的变化与否导出矛盾。

我们已经导出了这些联通块如此多的性质，现在让我们回到主线，试图用手上有的信息捏一个算法出来。我们考虑在这个联通树上做，从根也就是 $[s]_\omega$ 开始。假设我们现在处理到 $[v]_i$（将会保证它是极小孙），我们考虑进入时的 $\min(D([v]_i^-))>>i$，我们的目标将是扩展 $[v]_i^-$ 中所有 $d(u)>>i$ 等于这个值的 $u$（称为访问这个联通块）。

在实现它之前，让我们先来考虑怎么用这个功能实现 SSSP。我们考虑递归树的根 $[s]_\omega$，进入时 $\min(D([s]_\omega^-))>>\omega=0$，而我们要扩展联通块内（注意初始时 $S=\varnothing$）的所有点 $u$ 将要满足 $d(u)>>\omega=0$，而这个是必然实现的，换而言之就是我们将会扩展与 $s$ 联通的每个点。而我们每次扩展到的点 $v$ 都会满足 $[v]_0$ 是极小孙从而 $D(v)=d(v)$，也即一定合法。当然，在实现时，为了简化细节，我们可以选择先行用 $s$ 扩展一遍，这并不会影响总体复杂度，而可以规避一些奇怪的 $+\infty$ 问题。

（伪代码 2）

初始化 $S=\{s\}$。
初始化 $D(s)=0$，$D(v)=w(s,v)(v\not=s)$。
访问 $[s]_\omega$。

考虑如何实现这个访问，让我们先来推点性质。

如果 $i=0$ 直接扩展返回即可。否则，根据引理 13，由于进入时 $[v]_i$ 是极小孙，可知 $\min(D([v]_i^-))>>i=\min(d([v]_i^-))>>i$。在该扩展的扩展完前，右边是不会变的，进而左边也不会变，反过来这又通过引理 12 说明了在此期间 $[v]_i$ 会一直作为极小孙存在。

让我们维护一个 $ix([v]_i)$ 标识 $\min(D([v]_i^-))>>i-1$ 的值。我们考虑一个联通块 $[p]_{i-1}$ 是 $[v]_i$ 的儿子，则它是 $[v]_i$ 的小儿子当且仅当 $\min(D([p]_{i-1}^-))>>i-1=\min(D([v]_i^-))>>i-1=ix([v]_i)$，而 $[p]_{i-1}$ 是极小孙又等价于它是 $[v]_i$ 的小儿子。我们对于 $[v]_i$ 所有小儿子递归运行该算法，则对于小儿子 $[p]_{i-1}$，扩展到的点 $q$ 均满足 $d(q)>>i-1=\min(d([p]_{i-1}^-))>>i-1=\min(D([p]_{i-1}^-))>>i-1=\min(D([v]_i^-))>>i-1$，$d(q)>>i=\min(D([v]_i^-))>>i$ 进而成立。

当然我们观察到：同一次遍历中 $ix([v]_i)$ 可能需要有至多两种取值。解决方案也很简单，$ix([v]_i)$ 向上循环直到 $\min(D([v]_i^-))>>i=ix([v]_i)>>1$ 变大为止。当然事实上我们的 $ix([v]_i)$ 并不需要每次重算，根据引理 11，如果后续还需要用到这个 $ix([v]_i)$，那么由于访问结束时的 $ix([v]_i)>>1$ 恰增大一，$\min(D([v]_i^-))>>i$ 也恰增大一，事实上 $ix([v]_i$ 这个变量是可以留到下次访问这个联通块继续用的。

以上都是感性理解，接下来我们会给出一系列引理严谨证明这个算法的正确性。在此之前，先让我们整理一下导出的算法：

（伪代码 3）

（“访问”$[v]_i$：扩展 $[v]_i^-$ 中所有 $d(u)>>i$ 等于进入时 $\min(D([v]_i^-))>>i$ 的点 $u$。）

如果 $i=0$，扩展 $v$ 并直接返回。
如果 $[v]_i$ 先前未曾被访问过，用 $\min(D([v]_i^-))>>i-1$ 初始化 $ix([v]_i)$。
重复以下流程直到 $[v]_i^-$ 为空或 $ix(v[i])>>1$ 发生变化：
1. 重复以下流程直到 $[v]_i$ 不再存在一个儿子 $[p]_{i-1}$ 满足 $\min(D([p]_{i-1}^-))>>i-1=ix([v]_i)$：
  1. 取出满足如此条件的一个儿子 $[p]_{i-1}$ 并递归访问之。
2. 将 $ix(v[i])$ 增大一。

接下来我们将会证明上面那个算法的正确性。本质上，我们是需要证明这个算法能不重不漏访问到所有该访问的点就可以了。考虑对 $i$ 归纳。当 $i=0$ 时由引理 8 得证。若 $i-1$ 成立，我们接下来对于 $i$ 将进行证明。作为辅助，我们将声明以下两条性质：

$ix([v]_i)>>1=\min(D([v]_i^-))>>i=\min(d([v]_i^-))>>i$。
$ix([v]_i)\le\min(d([v]_i^-))>>i-1$。

当 $ix([v]_i)$ 被初始化时，$[v]_i$ 是极小孙，根据引理 8 这两条显然成立。接下来我们假设这两条在伪代码 3 的大循环开始时成立。

（引理 14）在 $\min(D([v]_i^-))>>i$ 变大之前，$[v]_i$ 依然是极小孙且这两条性质依然成立。

根据引理 12 和引理 8 容易导出 $[v]_i$ 依然是极小孙，并且 $\min(D([v]_i^-))=\min(d([v]_i^-))$ 成立。根据引理 10·改，$\min(D([v]_i^-))>>i-1$ 不减。我们观察到 $ix(v[i])$ 在单次访问中至多自增一次，此时 $[v]_i$ 已不再存在一个儿子 $[p]_{i-1}$ 满足 $\min(D([p]_{i-1}^-))>>i-1=ix([v]_i)$，换而言之，$ix([v]_i)\lt\min(D([v]_i^-))>>i-1$，因此对 $ix([v]_i)$ 的自增不会破坏第二条性质。另一方面，由于 $\min(D([v]_i^-))>>i=\min(d([v]_i^-))$ 尚未变大，第一条也成立。
（引理 15）在 $\min(D([v]_i^-))>>i$ 变大之前向下递归访问到的每一个点 $u$ 满足 $d(u)>>i=\min(D([v]_i^-))>>i$。

根据引理 14，这两条性质维持正确。我们考虑递归到 $[p]_{i-1}$。我们有 $ix([p]_{i-1})=\min(D([p]_{i-1}^-))>>i-1$ 成立。而 $\min(D([p]_{i-1}^-))>>i-1\ge\min(D([v]_i^-))>>i-1\ge\min(d([v]_i^-))>>i-1$，我们考虑与第二条性质联立，发现所有涉及到的不等号实际上都是等号。由此可知 $\min(D([p]_{i-1}^-))>>i-1=\min(D([v]_i^-))>>i-1$，这保证了 $[p]_{i-1}$ 是 $[v]_i$ 的小儿子，进一步是极小孙。根据归纳假设我们可知扩展到的每个点 $u$ 均满足 $d(u)>>i-1=\min(D([p]_{i-1}^-))>>i-1=ix([v]_i)$，从而 $d(u)>>i=\min(D([v]_i^-))>>i$。
（引理 16）在大循环终止之前，$\min(D([v]_i^-))>>i$ 变大。

反之，根据引理 14，有第一条性质成立，从而 $ix([v]_i)>>1=\min(D([v]_i^-))>>i$。由于 $\min(D([v]_i^-))>>i$ 没有变大，$[v]_i$ 也一定没有变空，但由此一来大循环的终止一定是由于 $ix([v]_i)>>1$ 变大，矛盾。

另一方面，我们还需要证明这个算法将会终止。我们考虑引理 16，$\min(D([v]_i^-))>>i$ 在循环结束时会被增大，根据引理 13，$\min(d([v]_i^-))>>i$ 也会随之增大。我们考虑在此之前访问到过的儿子 $[p]_{i-1}$。根据引理 15，$[p]_{i-1}$ 中已经不再有满足 $d(u)>>i=\min(D([v]_i^-))>>i$（初值）的点了，换而言之，我们该访问的所有点已经访问完毕了。由于 $\min(d([v]_i^-))>>i$ 增大，故而对于 $[v]_i$ 的任何一个儿子 $[q]_{i-1}$，有 $\min(D([q]_{i-1}^-))>>i-1\ge\min(D([v]_i^-))>>i-1\ge\min(d([v]_i^-))>>i-1$，从而在循环正常终止之前，不会再产生新的递归调用。

不考虑循环结束后 $[v]_i^-=\varnothing$（否则显然）。如此一来，根据引理 11，$\min(D([v]_i^-))>>i$ 的变大量恰好为一，从而第一条性质中的三个量一齐增大一，维护了它的成立。另一方面，$ix([v]_i)$ 成为了满足这一条的最小正整数（偶数），从而第二条性质也成立。根据引理 13，$\min(D([v]_i^-))>>i=\min(d([v]_i^-))>>i$ 从此永远成立，且 $ix([v]_i)$ 和 $\min(d([v]_i^-))>>i$ 在不访问 $[v]_i$ 期间不会发生变化，从而这两条性质依然成立。

如此一来，我们完成了对这个算法正确性的证明。

4. 向线性进发

让我们考虑上面那个算法最大的问题之一：$\omega$ 层的联通块树，很容易就能把节点数卡成带 $\omega$，从原理上就不可能消去。但我们考虑这样一件事情：要往儿子递归本质上是对于不同的联通块不同处理，如果整个联通块都没变，那向下递归一层其实意义不是很大。翻译成人话：我们考虑对于只有一个儿子的联通块把它压给儿子作为一个点处理（等于是建了一棵叶子结点的虚树），压出来的新树我们称之为 $\mathscr T$（为免有读者和笔者一样不认识，这个字母是 T）。

让我们来熟悉熟悉定义，比如推点性质。$\mathscr T$ 中的所有叶子就是每个 $[v]_0=\{v\}$，而其中存在的每个点都满足 $[v]_{i-1}\subset[v]_i$。我们考虑最小的 $r$ 满足 $G_r=G$，则 $\mathscr T$ 的根就是 $[v]_r$（们）。一个点 $[v]_i$ 的父亲就是在原树中最低的度不小于二的祖先。由于每个非叶节点的度数都不小于二，$\mathscr T$ 中的点数不会超过 $2n-1$。

在这篇文章接下来的部分，我们不再考虑原树中的父子关系，转而用这两个词指代 $\mathscr T$ 中。我们同样适配一下“小儿子”和“极小孙”的定义。定义一个节点 $[v]_i$ 的儿子 $[u]_j$ 是小儿子，当且仅当 $\min(D([u]_j^-))>>i-1=\min(D([v]_i^-))>>i-1$；而极小孙的定义则修正为从根到它一路都是小儿子。如此一来，$\mathscr T$ 上的一个节点是极小孙等价于它的联通块在原树上就是极小孙。

若一个节点被访问过，它的所有祖先一定同样如此。我们打算要做的是，对于每个被访问过的节点 $[v]_i$，将它的所有儿子 $[u]_j$ 根据 $\min(D([u]_j^-))>>i-1$ 装桶（还记得什么是桶吗？），换而言之，我们有一个桶的二维数组 $B$（注意它是个数组，也就是只能存储连续的状态），满足每个 $[u]_j$ 被存储在 $B([v]_i,\min(D([u]_j^-))>>i-1)$ 中。我们考虑依然使用 $ix([v]_i)$ 标识 $\min(D([v]_i^-))>>i-1$，那么 $[v]_i$ 的小儿子一定恰好是 $B([v]_i,ix([v]_i))$ 中的全员。

但我们考虑这个装桶本质上不是在进入一个节点的时候装它的所有儿子，这是效率低下的。对于访问一个节点 $[v]_i$，它在父亲节点 $[v]_j$ 上的装桶修正将是简单的：考虑 $\min(D([v]_i^-))>>j-1=iv([v]_i)>>j-i$，于是我们只要保证它被装入 $B([v]_j,iv([v]_i)>>j-i)$ 即可。我们接下来要解决的问题实际上是对于还没被访问过的点如何装桶，让我们一会再说，眼下先把 $B$ 的状态数刻画清楚，让我们再来点引理。

（引理 17）如果 $[u]_j$ 是极小孙 $[v]_i$ 的小儿子，$\min(d([v]_i))>>i-1\le\min(D([u]_j^-))>>i-1\le\max(d([v]_i))>>i-1$。

根据引理 8，$\min(d([u]_j^-))=\min(D([u]_j^-))$；另一方面，$[u]_j^-$ 是 $[v]_i$ 的非空真子集，于是成立显然。

让我们定义 $ix_0([v]_i)$ 表示 $\min(d([v]_i))>>i-1$，我们的目标则是找一个 $ix_\infty([v]_i)$ 满足其不小于 $\max(d([v]_i))>>i-1$。等找到之后，极小孙 $[v]_i$ 的所有小儿子，根据引理 17，都可以在 $B([v]_i,ix_0([v]_i)\cdots ix_\infty([v]_i)$ 之间找到；从另一个角度说，如果一个节点在这之间找不到，那么它也一定不是小儿子，可以暂且不去管它。让我们定义 $B([v]_i,t)$ 是一个有效状态，当且仅当 $ix_0([v]_i)\le t\le ix_\infty([v]_i)$。

另一方面，我们注意到 $[v]_i$ 作为无向图的联通块所拥有的良好性质，我们有 $\max(d([v]_i))\le\min(d([v]_i))+\sum_{e\in[v]_i}w(e)$，换而言之就是距离的极差不超过整个联通块中所有边的权值和。我们定义 $\Delta([v]_i)=\lceil\frac{\sum_{e\in[v]_i}w(e)}{2^{i-1}}\rceil$，同时取 $ix_\infty([v]_i)=\Delta([v]_i)+ix_0([v]_i)$，那么不难注意到这样的 $ix_\infty([v]_i)$ 一定是能够符合定义的。而我们现在所关注的，无非是 $\Delta([v]_i)$ 的和而已。

（引理 18）$B$ 中的有效状态数总和不超过 $4(n+m)$。

一个 $[v]_i$ 在 $B$ 上的有效状态数是

$$ix_\infty([v]_i)-ix_0([v]_i)+1=\Delta([v]_i)+1\lt2+\frac{\sum_{e\in[v]_i}w(e)}{2^{i-1}}$$

同时注意到 $\mathscr T$ 中的点数不会超过 $2n-1$，那么我们有有效状态数总和为

$$\sum_{[v]_i\in\mathscr T}{(ix_\infty([v]_i)-ix_0([v]_i)+1)}\lt 4n+\sum_{[v]_i\in\mathscr T}\frac{\sum_{e\in[v]_i}w(e)}{2^{i-1}}$$

让我们考虑交换一下求和顺序，那么后半部分就变成了

$$\sum_{e\in E}\sum_{[v]_i\in\mathscr T\land[v]_i\ni e}\frac{w(e)}{2^{i-1}}$$

于是我们接下来只需要证明

$$\forall e\in E,w(e)\sum_{[v]_i\in\mathscr T\land[v]_i\ni e}\frac1{2^{i-1}}\le4$$

而我们注意到，若有 $w(e)\in[2^j,2^{j+1})$，则 $[v]_i$ 收到来自 $w(e)$ 贡献的必要条件是 $i\ge j$，且对于相同的 $i$ 只会有一个联通块收到贡献。如此一来，我们即有

$$w(e)\sum_{[v]_i\in\mathscr T\land[v]_i\ni e}\frac1{2^{i-1}}\lt2^{j+1}\sum_{i\ge j}\frac1{2^{i-1}}\lt\frac{2^{j+1}}{2^{j-1}}=4$$

证毕。

我们接下来考虑如何用一个 $O(m)$ 长度的数组 $A_0\cdots A_N$ 存储 $B$ 的所有有效状态。对于 $\Delta([v]_i)$ 我们将在之后展示它的预处理，一并可求的还有 $ix_0([v]_i)$。换而言之，在初次访问到 $[v]_i$ 时，所有该准备的都已经就绪了。对于 $\mathscr T$ 中的节点定义一个偏序关系比如访问顺序，随后在初次访问到 $[v]_i$ 时计算 $N([v]_i)=\sum_{[u]_j\lt[v]_i}(\Delta([u]_j)+1)$，这个可以用前缀和简单优化。现在对于每个有效状态 $B([v]_i,t)$，我们把它转存到 $A(t-ix_0([v]_i)+N([v]_i))$；当然我们先前提到非小儿子也要装桶，所以我们把所有无效状态丢进一个垃圾桶 $A(N)$ 里。

我们考虑所有没有被访问过的点如何装桶。我们注意到，它们一定构成若干 $\mathscr T$ 的不交子树，换而言之，构成了一个森林 $\mathscr U$（U）。如此一来，一个未访问过的点是一个访问过的点的儿子当且仅当它是 $\mathscr U$ 中的某个根。我们在后面将会展示如何在线性时间内维护所有根 $[v]_i$ 的 $\min(D([v]_i^-))$（作为刻画 $\mathscr U$ 的优势，也作为装桶的瓶颈），这里我们先看看如果它成立，我们要如何完成这个事情：

（伪代码 4）

（“扩张”一个节点 $[v]_i$（$i\ge1$）：在第一次访问 $[v]_i$ 时被调用，用来初始化其儿子的装桶，顺便初始化 $ix_0([v]_i)$ 和 $ix_\infty([v]_i)$。）

将 $ix_0([v]_i)$ 赋值为 $\min(D([v]_i^-))>>i-1$。
将 $ix_\infty([v]_i)$ 赋值为 $ix_0([v]_i)+\Delta([v]_i)$。
把 $[v]_i$ 从 $\mathscr U$ 中删去，将其所有儿子作为根加入。
对于 $[v]_i$ 的每个儿子 $[u]_j$，把 $[u]_j$ 装入 $B([v]_i,\min(D([u]_j^-))>>i-1)$。

当然这里我们只处理了 $i\ge1$。对于 $i=0$，我们实际上会扩展这个节点并改变一些点的 $D$ 值，这样我们就有必要把它重新装桶，让我们也来具化一下这部分：

（伪代码 5）

（“扩展”一个节点 $[v]_i=\{v\}$（$i=0$）：更新它的出边。）

将 $v$ 加入 $S$ 中。
对于每条出边 $(v,u)$，如果 $D(v)+w(v,u)\lt D(u)$：
1. 设 $[u]_j$ 是 $[u]_0$ 在森林 $\mathscr U$ 上的根，而 $[u]_i$ 是 $[u]_j$ 的父亲。
2. 将 $D(v)+w(v,u)$ 赋给 $D(u)$。如果这改变了 $\min(D([u]_j^-))>>i-1$，那么把 $[u]_j$ 装入 $B([u]_i,\min(D([u]_j^-))>>i-1)$。

注意到我们以上做的这些装桶工作都是为了优化伪代码 3 那个访问节点的操作，现在我们可以准备动手实现它了。回顾一下我们的目标和操作，它们都可以被合理地修改。我们要做的是扩展 $[v]_i^-$ 中所有 $d(u)>>j-1$ 等于进入时 $\min(D([v]_i^-))>>j-1$ 的点 $u$（$[v]_j$ 是 $[v]_i$ 的父亲）。我们依然维护 $ix([v]_i)$ 标识 $\min(D([v]_i^-))>>i-1$。如此一来，$[v]_i$ 的小儿子一定在 $B([v]_i,ix([v]_i))$ 中。另一方面，根据 $\mathscr T$ 的定义，$[v]_i=[v]_{j-1}$。由此一来，我们又有 $ix([v]_i)>>j-i=\min(D([v]_{j-1}^-))>>j-1$。根据引理 12，在 $ix([v]_i)>>j-i$ 变大前，$[v]_i$ 最小孙的性质依然保留，与之一同保留的还有上面那条小儿子的位置性质。至于向下递归的正确性，它的证明几乎完全没有变化。

和先前不同的是，这一次我们还需要维护我们的桶。把这些融合起来，我们得到了以下的算法：

（伪代码 6）

（“访问”$[v]_i$：扩展 $[v]_i^-$ 中所有 $d(u)>>j-1$ 等于进入时 $\min(D([v]_i^-))>>j-1$ 的点 $u$ 并正确维护 $[v]_j$ 上的桶，其中 $[v]_j$ 是 $[v]_i$ 的父亲，不存在则取 $j=\omega+1$。）

如果 $i=0$，（伪代码 5）扩展 $v$ 并直接返回。
如果 $[v]_i$ 先前未曾被访问过，（伪代码 4）扩张 $[v]_i$ 并用 $ix_0([v]_i)$ 初始化 $ix([v]_i)$。
重复以下流程直到 $[v]_i^-$ 为空或 $ix([v]_i)>>j-i$ 发生变化：
1. 重复以下流程直到 $B([v]_i,ix([v]_i))$ 为空：
  1. 取出 $B([v]_i,ix([v]_i))$ 中的一个儿子 $[p]_k$ 并递归（伪代码 6）访问之。
2. 将 $ix(v[i])$ 增大一。
如果 $[v]_i$ 不是根且 $[v]_i^-\not=\varnothing$：将 $[v]_i$ 移到 $B([v]_j,ix([v]_i)>>j-i)$。
如果 $[v]_i$ 不是根且 $[v]_i^-=\varnothing$：将 $[v]_i$ 从 $[v]_j$ 的桶中删去。

这里我们会证明这个算法的正确性。感性上而言这个事情十分显然，但严格论证相当繁琐，这里笔者相信读者水平，选择精简部分冗长证明（比如把归纳假设抄一遍然后推一个显然的不等式，可能会直接把不等式的前置条件写出来然后说直接归）；省流：更注重算法本身的话可以直接过掉，跳到命题 27。

我们先在这里挂一个之前证过的东西：

（引理 19）伪代码 6 的正确性可以导出伪代码 2 中 SSSP 算法的正确性。

回到算法本身，方便起见，我们定义：

一个性质是“访问维护”的，代表我们假设在进入一个访问函数时它成立，且可以保证结束访问函数时它依然成立。
一个性质是“逐步维护”的，代表我们假设在开始算法任意一步前它成立，且可以保证结束这一步之后它依然成立。

那么我们可以维护这一列东西：

$[v]_i$ 在进入函数时是极小孙。（这个的证明要比其他的错位一点。）
（逐步维护）$[v]_i$ 前被访问过的点当时是极小孙。
函数扩展到的点 $u$ 是 $[v]_i^-$ 中所有 $d(u)>>j-1$ 等于进入时 $\min(D([v]_i^-))>>j-1$ 的点。
（访问维护）$[v]_i$ 的桶被正确维护。
（逐步维护）$[v]_i$ 被访问过的所有后代的桶被正确维护。
（逐步维护）每个被访问过的点的没有被访问过的儿子的桶被正确维护。
如果 $i\ge1$，那么有如下两条性质在大循环中成立：
（性质甲，访问维护）$ix([v]_i)>>j-i=\min(D([v]_i^-))>>j-1=\min(d([v]_i^-))>>j-1$。
（性质乙，逐步维护）$ix([v]_i)\le\min(d([v]_i^-))>>i-1$。
（逐步维护）$[v]_i$ 被访问过的所有后代满足以上两条性质成立。

让我们对 $i$ 归纳说明这八点。

（引理 20）$i=0$ 时算法正确，也即上面八条性质成立。

注意 5,7,8 在 $i=0$ 时不起效，进入时的 1 和 2 可以直接推 2，1 错位处理，那我们只需要关心 3,4,6。根据引理 8，$d(v)=D(v)=\min(D([v]_i^-))$，于是 3 显然成立。由于伪代码 5 维护的是 $\mathscr U$ 的根的装桶，6 也一定成立。至于 5，伪代码 6 的最后一行说明了这一点。

我们接下来试着去证明：如果对 $[v]_i$ 的所有儿子都有这八条性质成立，那它们对 $[v]_i$ 也成立。

（引理 21）在一次递归里第一次进循环的时候我们的算法正确且性质甲被满足。

如果 $[v]_i$ 不是第一次被访问（不考虑 $i=0$），那递归上来干的第一件事情就是进循环，这个时候算法根据归纳假设显然正确，性质甲根据 7 被满足。

如果 $[v]_i$ 第一次被访问，我们分开考虑循环前干的两件事情：扩张与初始化。扩张显然至多影响 6 的成立，而根据扩张的流程，6 的正确性同样是显然的。而初始化只会影响 7。考虑扩张的具体流程，这个初始化实际上就是在做一个用 $\min(D([v]_i^-))>>i-1$ 初始化 $ix([v]_i)$。根据引理 8 我们可以推出甲和乙成立。不过值得注意的是，这里是为了后续方便而进行的额外证明。单就这个引理而言，有一个很好笑的事情叫做 7 实际上啥也没讲，因为我们压根还没进大循环。
（引理 22）如果在开始访问 $[p]_k$ 时 $\min(D([v]_i^-))>>j-1$ 还没有变大，那么所有访问时的假设都成立，而且有 $ix([v]_i)=\min(D([v]_i^-))>>i-1=\min(D([p]_k^-))>>i-1$ 成立。

我们首先要证明的是访问的合法性也即 $[p]_k$ 是极小孙。根据 1 和引理 12，我们可以推出此时 $[v]_i$ 是极小孙，那么我们要证明的实际上是 $[p]_k$ 是小儿子。根据 4 和 5，既然 $[p]_k$ 在 $B([v]_i,ix([v]_i))$ 中被取出，那么一定有 $ix([v]_i)=\min(D([p]_k^-))>>i-1$。另一方面，我们有：

$$ \begin{aligned} \min(D([p]_k^-))>>i-1\ge&\min(D([v]_i^-))>>i-1\\ \ge&\min(d([v]_i^-))>>i-1\\ \ge&ix([v]_i) \end{aligned} $$

（第三个等号是性质乙。）

总之这三个不等号全都得取等。那么我们就有了 $ix([v]_i)=\min(D([v]_i^-))>>i-1=\min(D([p]_k^-))>>i-1$，第二个等号可以推出 $[p]_k$ 是小儿子。

至于 2,5,6,8 这四个逐步维护的东西。对于 2 和 6，递归下去本身没啥差别。5 根据 4 和 5 归，8 根据 7 和 8 归。至于 3，它本身不是一个访问时的假设，等于啥也没说。
（引理 23）如果在开始访问 $[p]_k$ 时 $\min(D([v]_i^-))>>j-1$ 还没有变大，那么这个递归访问正确。

根据归纳假设，递归访问本身肯定是对的，我们要关注的只是递归访问中的每一步对于 $[v]_i$ 那一串性质的影响。

老规矩无视 2 和 6。再带个 3，由于 $j\gt i$ 和引理 22 再带上 $\min(D([v]_i^-))>>j-1$ 不变大的性质可以直接归。

还是老规矩来捆绑考虑 5 和 8。我们考虑所有在递归期间没有被归纳维护的点，它们是 $[v]_i$ 被访问过的后代但不是 $[p]_k$ 的后代，我们从中随便薅一个 $[o]_g$ 出来考虑。我们注意到，这个点没有在递归访问中被涉及，这意味着 $ix([o]_g)$ 不变，$[o]_g$ 本身也未曾被重新装桶。根据 8 之前的成立性，甲和乙之前是成立的。注意到 $\min(d([o]_g^-))$ 显然的不变性（联通块内根本没变而 $d$ 是常值函数），乙显然还是没啥问题的。根据性质甲，我们得知 $\min(D([o]_g^-))>>j-1=\min(d([o]_g^-))>>j-1$。右边不减，左边不增，但左边不会小于右边，所以等号依然成立。那么 8 显然还是对的，5 由于该装的桶没有变化所以也还是对的。

我们唯一还需要考虑一下的是性质甲对于 $[v]_i$ 的成立。左边没变，中间根据假设没变，右边只会变大但会被中间压制，那么归完了。
（引理 24）如果 $\min(D([v]_i^-))>>i-1=\min(d([v]_i^-))>>i-1$，那么大循环里的第二步正确。

显然这步只会影响到性质乙。我们发现，进入第二步的充要条件是 $B([v]_i,ix([v]_i))$ 为空，那么根据 5 和 6，再考虑到 $\min(D([v]_i^-))>>i-1$ 一定在某个儿子上得以复现，我们可知 $ix([v]_i)\not=\min(D([v]_i^-))>>i-1$，进而 $ix([v]_i)\not=\min(d([v]_i^-))>>i-1$。于是我们把性质乙在这一步前的等号给扬了，给左边加一之后最多也就是等号回来，性质乙依然成立。
（引理 25）在 $\min(D([v]_i^-))>>j-1$ 变大前，大循环正确执行但不会终止。

根据引理 23，大循环里的第一步没问题；根据引理 12，$[v]_i$ 依然是极小孙；根据引理 8，$\min(D([v]_i^-))=\min(d([v]_i^-))$，进而导出引理 24 可用。如此一来，我们的循环本身显然是正确的。

至于不终止性，我们只需要考虑 $[v]_i^-$ 为空或 $ix(v[i])>>j-i$ 发生变化——大循环的终止条件——要如何不成立即可。前者显然与 $\min(D([v]_i^-))>>j-1$ 不变大矛盾。对于后者，考虑引理 21，我们得到进循环时有 $ix([v]_i)>>j-i=\min(D([v]_i^-))>>j-1=\min(d([v]_i^-))>>j-1$。而根据性质乙和引理 24，可知 $ix([v]_i)\le\min(d([v]_i^-))>>i-1=\min(D([v]_i^-))>>i-1$，进而 $ix([v]_i)>>j-i\le\min(d([v]_i^-))>>j-1=\min(D([v]_i^-))>>j-1$。由于右边不变，左边显然也不能变。证毕。
（引理 26）当 $\min(D([v]_i^-))>>j-1$ 变大时，大循环正确终止。

很显然，$\min(D([v]_i^-))>>j-1$ 的变大一定出现在对儿子 $[p]_k$ 的递归访问中。根据引理 23，这次递归访问本身肯定是正确的。在这次递归访问结束时，根据 5 和 6 我们得知在 $ix([v]_i)$ 被加到 $\min(D([v]_i^-))>>i-1$ 前一定不会再触发任何一次递归。而在此之后，考虑引理 21 所推出的 $ix([v]_i)>>j-i=\min(D([v]_i^-))>>j-1$，可知左边一定变大，大循环正确终止。

在这次递归访问之前，几乎所有性质已经被我们证明完毕；而在此之后，所剩下的仅仅是几次 $ix([v]_i)$ 的增大。这些步骤有利于说明函数扩展到的点 $u$ 是 $[v]_i^-$ 中所有 $d(u)>>j-1$ 等于进入时 $\min(D([v]_i^-))>>j-1$ 的点，但我们还需要说明我们扩展到了所有这样的点。事实上，如果 $[v]_i$ 一整个被访问空了，那么显然；反之，让我们设让 $\min(D([v]_i^-))>>j-1$ 变大的那次扩展是对于 $u$。根据引理 11，变大量恰好是一；再根据引理 13，$\min(d([v]_i^-))>>j-1$ 一同变大。那么 3 的正确性就非常显然了。

当我们退出大循环时，$ix([v]_i)>>j-i$ 变大而且恰好卡在正好变大一。由于 $\min(d([v]_i^-))>>j-1$ 变大，性质乙的正确性保留。由于左中右都增大一，性质甲也依然是正确的。这使得 8 的正确性得以维持。根据性质甲，我们知道我们大循环后的重装桶是正确的，那么 4 无误。

证毕。

综合以上几条（20,21,25,26），我们可以得到一个综合性的概论：

（命题 27）假设联通块树 $\mathscr T$ 已经被构建且 $\mathscr U$ 中的根的 $\min(D([v]_i^-))$ 可以以总和线性的时间维护，那么 SSSP 的总复杂度可以不超过 $O(m)$。

事实上时空代价摊下来只需要考虑桶，交给引理 18 就好。这里原论文写了一大段非常严谨的东西，由于这只是个学习笔记所以可以直接写显然。

5. 联通块树

考虑命题 27 的两个前置条件——$\mathscr T$ 的线性预处理和 $\mathscr U$ 信息的线性维护。我们接下来将逐个击破这两点来把我们的算法加速到线性。

首先是联通块树。我们考虑本质上我们对于一条权为 $x$ 的边实际上只关心 $2^i\gt x$ 的最小 $i$。换而言之，我们实际上只关心 $\operatorname{msb}(x)$（这个函数表示二进制最高位也即 $\lfloor\log_2x\rfloor$）。我们转换边权后会意识到本质上关心的是只保留一部分权值较小的边时全图的连通状态；细化到两个点 $u$ 和 $v$ 的话，其实只关心从 $u$ 到 $v$ 的路径上最大值的最小值。我们注意到有经典结论为这条路一定是在最小生成树上走的，那么我们考虑对转换过边权的图先盘一棵最小生成树出来。原论文指出线性 MST 在先前的论文中已被解决，但笔者翻阅引用论文后发现它涉及到一个叫“原子堆”的复杂数据结构。事实上在这一步存在更方便的处理方法，参见：力大砖飞 2。

那么我们的联通块就可以直接在 MST 上刻画了。具体而言，假设我们求出来的最小生成树是 $M$，那么对于 $G_i$（定义在 #3 一上来），我们考虑仅保留在 $M$ 中的边，构成 $M_i$。我们进一步定义 $[v]_i^M$ 是 $v$ 在 $M_i$ 中所属的联通块。有一个显然的性质：$[v]_i$ 和 $[v]_i^M$ 涵盖完全相同的顶点。更进一步，$[v]_i^M$ 一定是 $[v]_i$ 的一棵生成树（事实上一定是最小生成树）。据此，我们可以推出以下这行不等式：

$$\operatorname{diameter}([v]_i)\le\operatorname{diameter}([v]_i^M)\le\sum_{e\in[v]_i^M}w(e)\le\sum_{e\in[v]_i}w(e)$$

注意到我们的 $\Delta$ 只关心直径如何，所以我们可以把 $\Delta([v]_i)$ 重定义为 $\lceil\frac{\sum_{e\in[v]_i^M}w(e)}{2^{i-1}}\rceil$。事实上，由于 $M$ 只有 $n-1$ 条边，我们桶的数量可以一并被压到 $8n$ 以内。如此一来我们发现和桶相关的部分全都被压到了 $O(n)$，换而言之我们的算法除了调用结构还是 $O(m)$ 的以外已经全面 $O(n)$ 了，虽然好像并没有什么用。

至于 $M$ 比 $G$ 好在哪里呢？十分显然，它是一棵树，而树上可以干很多事情，比如线性的并查集。

现在我们考虑把树上的所有边按转换后的边权排序（由于先前已经成功实现了转换边权的离散化，这里一个计数排序就能乱杀），为 $e_1,e_2,\cdots,e_{n-1}$。补充定义 $\operatorname{msb}(w(e_0))=-1$ 与 $\operatorname{msb}(w(e_n))=\omega$。那么我们注意到：

$$\operatorname{msb}(w(e_i))\lt\operatorname{msb}(w(e_{i+1}))\iff M_{\operatorname{msb}(w(e_i))+1}=M_{\operatorname{msb}(w(e_{i+1}))}=(V,\{e_1,e_2,\cdots,e_i\})$$

如此一来就好办多了。我们从 $1$ 到 $n-1$ 顺次合并 $e_i$ 的两端，每次发现转换边权和下一条不一样就说明该给树里加点边了。这部分多说无益，直接伪代码可能比较好理解。

（伪代码 7）

（生成树构建。）

（变量阐述：$c$ 是每个节点在过程中的所属编号（会维护更新），$c'$ 是用于 $c$ 更新的临时数组，$X$ 为存当前还有哪些点要找爹的临时数组，$X'$ 存 $X$ 中所有点各自在并查集中的根，$f$ 表示每个点的爹（编号对编号）。我们另外维护一个计数器 $c$ 表示目前开了几个点，注意不要混淆。）

对于每个 $v$，把 $c(v)$ 赋值为 $v$。
顺次遍历每条边 $(u,v)$，假设现在是第 $i$ 条：
1. 将 $find(u)$ 和 $find(v)$ 并入 $X$ 中。（$find$ 是并查集找根。）。
2. 合并 $u$ 和 $v$，并维护好联通块内边权和。
3. 如果第 $i+1$ 条边的 $\operatorname{msb}$ 比现在的边大：
  1. 对每个 $X$ 中的点进行 $find$，结果存入 $X'$。
  2. 为 $X'$ 中的每个点分配新编号（每次分配 $c$ 并将其自增）存在 $c'$ 中。
  3. 对 $X$ 中的每个点 $v$ 将 $f(c(v))$ 赋为 $c'(find(v))$。
  4. 对 $X'$ 中的每个点 $v$ 用 $c'(v)$ 覆盖 $c(v)$，然后初始化这个新联通块的 $\Delta$ 和层级（$\operatorname{msb}(u,v)+1$）。
  5. 清空 $X$。

于是我们现在有了一条显然的结论：

（命题 28）联通块树 $\mathscr T$ 可以被线性构建。

6. 未至之境

不知道犯什么中二起这个名字，总之就是说，$\mathscr U$ 怎么办。我们整理一下对树上要维护的 $D$ 都做了什么，会发现一共只有两类：

减小一个叶子的权值；
查询一个列表中的子树内所有叶子权值的最小值。
将一棵子树从列表中删去，并将它的所有儿子加入。

不难想到把树拍到 dfs 序上。那么我们要解决的就变成了这样一个问题：给定一个序列（初始为全 $+\infty$）和一个区间列表（初始为全序列），支持两种操作：

单点减小；
区间（保证在列表中）查最小值；
将一个区间在列表中分裂为两半。

假设我们要处理 $m$ 次单点减和 $n$ 次区间分裂（根据应用场景性质，不妨 $m=\Omega(n)$），那么：

（引理 29）我们可以在 $O(n\log n+m)$ 的复杂度内解决这个问题。

直接一棵线段树莽上去，静态维护每个列表区间的最小值，分裂的时候重新查询就好。

现在我们要考虑如何优化这个东西。我们会想到可能要涉及类似分块的思路。预定义 $T(m,n,s)$ 表示上面这个问题的最优处理复杂度，但是初始列表中的区间长度不超过 $s$。

（引理 30）$T(m,n,s)=O(m+n\log s)$。

直接对初始列表中的每段开线段树即可，之后参见引理 29。
（引理 31）$T(m,n,s)\le O(m)+T(m,n,\log s)+T(m,\frac n{\log s},\frac s{\log s})$。

序列按 $\log s$ 分块，块间块内分别向下递归即可。

两个引理综合一下我们有：

（引理 31·改）$T(m,n,s)\le O(m)+T(m,n,\log s)$。

把引理 31 第三个式子用引理 30 代掉就行。
（引理 32）$\forall i\ge0$ 有 $T(m,n,n)\le O(im)+T(m,n,\log^{(i)}n)$。其中第三个参数指对 $n$ 连开 $i$ 次 $\log$。

引理 31 向下递归一下就行。
（引理 33）在 $O(n)$ 的预处理时间内，我们可以生成一种数据结构维护正整数（个数在 $O(\sqrt[4]{\log n})$），满足在常数时空内加数，删数和给定数查排名。

只是复读了一下 Q 堆的定义。不会 Q 堆的不用太在意反正知道有这个就行，要学的话可以看《Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths》。
（引理 34）在 $O(n)$ 的预处理时间内，我们可以生成一种数据结构维护正整数序列（长度在 $s=O(\sqrt[4]{\log n})$），满足在常数时空内单点修改，区间查最小值。

我们维护另一个序列表示离散化后的结果。注意到由于原序列很短所以整个新序列比特数不超过 $s\times\log s=O(\omega)$，可以一整个用一个二进制单位给压在一起。对于单点修改，我们发现对新序列本质的影响在于单点修改和其他位置的相应调整。这或许听起来很困难，但实际上我们注意到一共只有 $s^s$ 种本质不同的新序列和 $s^2$ 种本质不同的修改，而这俩乘起来再带个 $s$ 都不到 $O(n)$。所以我们直接打表预处理暴力做就行。至于区间查最小值——没错我们继续打表就可以了。
（引理 35）$T(m,n,\sqrt[4]{\log n})=O(m)$。

序列按 $\sqrt[4]{\log n}$ 分块即可。
（命题 36）$T(m,n,n)=O(m)$。

引理 32 取 $i=2$ 然后上引理 35 即可。

7. 碎碎念

综合以上这些我们得到了整个问题的最终结论：

（命题 37）存在无向连通图正整数边权的线性时空单源最短路算法。

其他的……那个 Q 堆实际上只有在 $n$ 大得离谱的时候才有效，事实上在正常的应用环境下直接暴力做复杂度没区别。不用 Q 堆的话 Gabow 给了一个单 $\alpha$ 的算法，晚点补。

总而言之，做完了……捏。

笔者才疏学浅，如果哪里有笔误或奇怪的 bug 还请不吝赐教。

至此，且容我暂且搁笔。

return20071007的博客

博客

【理性愉悦】无向连通图正整数边权线性时空单源最短路浅析