正整数边权无向图单源最短路线性算法——Thorup 算法

Eznibuil · 2023-03-22 21:41:26 · 算法·理论

该篇不完整，可以参阅 cancan123456、Greturn。感谢他们。

由于公式较多，加载可能卡顿，请酌情关闭 JS 防止浏览器炸锅。

若所有的单个数据均能在装进长度为 \omega 的字且将字的运算视作 O(\omega)，则 Thorup 算法时间复杂度为 O(n+m)（请注意这里的 n 和 m 指的是存储规模，亦即隐含 \omega 因子）。严格地说，乘法超过了 O(\omega)，但是可以证明不使用乘法时间复杂度为 O(m\alpha(m,n))，其中 \alpha 是反阿克曼函数。

原载 Journal of the ACM, vol. 46, No. 3, May 1999, pp. 362–394。

Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time - Mikkel Thorup

Upd 2023.8.24：找到了一篇效率对比的文章，可以看出 Thorup 的 misscache 非常严重：https://www.researchgate.net/publication/258649654_Performance_of_Thorup's_Shortest_Path_Algorithm_for_Large-Scale_Network_Simulation。

放个 Java 实现：https://github.com/npruehs/thorup/blob/master/de/unikiel/npr/thorup/algs/Thorup.java。

放个 Python 实现：https://github.com/SingularBunny/shortest-path-problem/blob/master/thorup/algs/thorup.py。

写这个是因为可恶的 [CSP-S 2021] 交通规划。

浅浅地放一个有向图单源负权最短路最优（2023.4.11）：https://arxiv.org/abs/2304.05279。以及 EI 的略解。

人肉论文翻译如下。翻译者：Eznibuil、DeepL。转载请注明出处并附上链接。有错请私信。Upd：发现 DeepL 翻译经常漏句子，可惜我不可能重新人工翻译一遍，所以发现漏的请私信。

摘要 \quad%Eznibuil 单源最短路径问题（SSSP）是图论算法中的经典问题之一：给定一个源点 s 的正权图 G，找出从 s 到图中所有其他节点的最短路径。

自 1959 年以来，一般有向图和无向图的 SSSP 的所有理论发展都是基于 Dijkstra 算法，按照与 s 的距离增加的顺序访问节点。因此，Dijkstra 算法的任何实现都是根据节点与 s 的距离来排序的。

在此，我们提出了一种确定性的线性时间和线性空间算法，用于解决具有正整数权重的无定向单源最短路径问题。该算法通过建立一个分层的桶状结构来避免排序瓶颈，确定可能以任何顺序被访问的节点对。

分类和主题描述符：F.1.1 [抽象设备的计算]：计算模型——有界行动设备（随机存取机）；F.2.2 [算法和问题复杂性的分析]：非数字算法和问题——离散结构的计算，排序和搜索；G.2.2 [离散数学]：图算法——离散结构上的计算，排序和搜索

一般术语： 算法

其他关键词和短语： RAM 算法、最短路径

（页脚注释）

一个初步的简短版本在这里出现了：Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS ’97). IEEE Computer Society Press, Los Alamitos, Calif., pp. 12–21.

其中一些工作是在作者在哥本哈根大学时完成的。

作者地址：AT&T Labs, 180 Park Avenue, Florham Park, NJ 07932，邮箱：[email protected]。

允许为个人或课堂使用本作品的部分或全部内容制作数字/硬拷贝，但不得以营利或商业利益为目的制作或分发拷贝，必须显示版权声明、出版物名称及其日期，并声明拷贝是经美国计算机协会（ACM）的许可。以其他方式复制，重新出版，在服务器上发布，或重新分配到列表中，需要事先获得具体的许可和/或收费。

© 1999 ACM 0004-5411/99/0500-0362 ＄5.00

1.%Eznibuil 简介

令 G=(V,E),|V|=n,|E|=m，是一个无向连通图，且带有一个正整数边权函数 \ell:E\to\N^+（原文为 \N 因为旧时自然数不含 0）以及一个源点 s\in V。如果 (v,w)\notin E，定义 \ell(v,w)=\infty。则单源最短路径（SSSP）问题是对于每一个节点 v 找到 d(v)=dist(s,v) 亦即从 s 到 v 的最短路。这是图论最经典的问题之一。在这篇论文中，我们将给出一种确定性的线性时间线性空间的对于正整数边权无向图的 SSSP 算法。迄今为止只有一个线性的 SSSP 算法但仅限平面图 [Henzinger et al. 1997]。

1.1 模型 \quad%Eznibuil 我们的算法在 RAM 上运行，它模拟了我们在命令式编程语言（如 C）中的编程。内存是划分为若干长度为 \omega 的可寻址的字。字里面也会存储本身的地址，所以 \omega\ge\log n。更多的，我们还有常数个数的寄存器，每个大小为一个字。基本的汇编指令有：条件跳转、直接和间接寻址，用于加载和存储寄存器中的字；以及一些计算指令，如比较、加法和乘法，用于操作寄存器中的字。空间复杂度定义为最大使用的地址，而时间复杂度则是指令的数量。假设所有的权值和距离为整数，它们将被解释为二进制串。为了简化问题，假设所有的权值和距离都可以存进一个字，这样输入和输出的复杂度就是 O(m)；否则，如果源点只连一条边，且边权非常大，那么除了源点的最短路都会非常大，使得输出规模大大超过输入规模。我们的算法很容易修改为对于任意大的整数权重在时间和空间上都是线性运行。

在 RAM 模型中，人们可能倾向于只使用计算指令中的 \text{AC}^0 操作。如果一条计算指令可以由一个 \omega^{O(1)} 大小的具有 O(\omega) 输入和输出位的恒定深度电路来计算，那么它就是一个 \text{AC}^0 操作。在电路中，我们可能有非门和与门以及或门的无界扇入。加法和位运算都是 \text{AC}^0 运算。另一方面，乘法则不是。我们的线性时间算法确实使用了乘法，但如果我们把自己限制在 \text{AC}^0 操作上，它可以在 O(\alpha(m,n)m) 时间内实现。

与 RAM 相比，我们有指针机模型，不允许进行地址运算，因此，对我们的算法来说，桶是必不可少的。此外，我们还有基于比较的模型，其中权重只能被比较。在下面提到的所有算法中，只有 Dijkstra [1959]、Williams [1964] 以及 Fredman 和 Tarjan [1987] 的算法在这两种限制性模型中都能工作。所有其他的算法都假设了一个具有整数权重的 RAM 模型，就像我们一样。

1.2 历史 \quad%Eznibuil 自 1959 年以来，一般有向或无向图的 SSSP 的所有理论发展都是基于 Dijkstra 的算法 [Dijkstra 1959]。对于每一个节点我们有一个超距 D(v)\ge d(v)。更多的，我们还有一个集合 S\subseteq V 满足 \forall v\in S:D(v)=d(v) 且 \forall v\notin S:D(v)=\min_{u\in S}\{d(u)+\ell(u,v)\}。最初，S=\{s\} 且 D(s)=d(s)=0 且 \forall v\ne s:D(v)=\ell(s,v)。对于算法的每一轮，我们访问一个 v\notin S 且拥有最小的 D(v)。接着，就像 Dijkstra 证明的那样，D(v)=d(v)，所以我们将 v 加入集合 S。因此，对于所有的 (v,w)\in E，若 D(v)+\ell(v,w)<D(w)，则我们需要把 D(w) 松弛为 D(v)+\ell(v,w)。当 S=V 时 Dijkstra 算法结束，返回 D(\cdot)=d(\cdot)。

Dijkstra 的时间复杂度取决于 n-1 找到最小 D(v) 的 v\in V\setminus S 以及至多 m 次松弛一些 D(w)。随后所有针对一般图的 SSSP 的理论发展都是基于支持这两种操作的优先队列/堆的各种加速和权衡。如果我们只单纯扫一遍所有点来找到最小，我们以 O(n^2+m) 解决了 SSSP。应用上 Williams 的堆 [Williams 1964]，我们得到 O(m\log n) 的时间。Fredman 和 Tarjan 的斐波那契堆 [Fredman and Tarjan 1987] 专用于 SSSP，并将运行时间降低到了 O(m+n\log n)。他们指出，这是 Dijkstra 算法在比较模型中的最佳实现，因为 Dijkstra 算法是按照排序顺序访问节点的。使用 Fredman 和 Willard 的聚合树，我们得到一个 O(m\sqrt{\log n}) 随机下的期望界 [Fredman and Willard 1993]。他们随后的 atomic heap（直译为“原子堆”）给出了 O(m+\frac{n\log n}{\log\log n}) 的界 [Fredman and Willard 1994]。更近些，Thorup 的优先队列给出一个 O(m\log\log n) 的界和一个 O(m+n\sqrt{\log n}^{1+\varepsilon}) 的界 [Thorup 1996]。假设我们想要线性空间，这些界是随机的。最后，Raman 获得了一个在确定性的线性空间中 O(m+n\sqrt{\log n\log\log n}) 的界和一个随机下 O(m+n\sqrt[3]{\log n}^{1+\varepsilon}) 的界 [Raman 1997]。

在最大边权 C 的基础上也有了很大的发展，同样是假设整数的边权，每个都可填入一个字。首先注意到使用 van Emde Boas 的普通搜索结构 [van Emde Boas 1977; van Emde Boas et al. 1977; Melhorn and Nähler 1990]，并使用 \lfloor\frac{D(v)}n\rfloor 装入桶，我们得到一个 O(m\log\log C) 的 SSSP 算法。Ahuja、Melhorn、Orlin 和 Tarjan 找到了一个用于 SSSP 的优先队列使得运行时间为 O(m+n\sqrt{\log C}) [Ahuja et al. 1990]。最近，这被 Cherkassky 等人 [1997] 证明为 O(m+n\sqrt[3]{\log C\log\log C}) 的期望时间，以及被 Raman [1997] 进一步地优化到 O(m+n(\log C)^{\frac14+\varepsilon})。对于无向图的情况，我们通过提出一个 O(m) 算法来结束上述探索。

1.3 技术 \quad%Eznibuil 正如 Fredman 和 Tarjan [1987] 所观察到的，在线性时间内实现 Dijkstra 的算法将需要在线性时间内进行排序。事实上，反之亦然，Thorup 已经证明线性时间排序意味着 Dijkstra 算法可以在线性时间内实现 [Thorup 1996]。在本文中，我们以 O(m) 的时间和空间确定性地解决 SSSP 的无向版本。由于我们不知道如何在线性时间内排序，这意味着我们偏离了 Dijkstra 的算法，即我们不按与 s 的距离增加的顺序访问节点。我们的算法是基于分层的桶状结构，其中桶状结构有助于识别可以按任何顺序访问的节点对。应该提到的是，使用桶状结构本身并不是与 SSSP 有关的新方法。1978 年，Dinitz [Dinic 1978] 认为，如果 \delta 是最小的边权，那么在 Dijkstra 的算法中，我们可以访问任何最小化 \lfloor\frac{D(v)}\delta\rfloor 的节点 v。因此，根据 \lfloor\frac{D(v)}\delta\rfloor 进行分桶，我们可以以任何顺序访问最小桶中的节点。在本文中，我们在某种意义上是在递归地应用 Dinitz 的思想，确定跨越边的最小权 \delta 较大的割。

1.4 目录 \quad%Eznibuil 本文分述如下： 在第 2 节的初步介绍之后，在第 3 节中，我们提出了使用桶来避免排序瓶颈的一般想法。然后在第 4-8 节中递归地实现了这一想法，使我们在第 9 节中总结出了正整数权重的无定向 SSSP 问题的线性时间算法。最后，在附录 A 中，我们讨论了在权重不是整数而是浮点数的情况下如何获得线性时间算法。

2.%Eznibuil 预备工作

整个论文中，我们会沿用在简介中 Dijkstra 算法定义的 G,V,E,\ell,s,D,d,S。特别的，关于 S 和 D，\forall v\in S:D(v)=d(v) 且 \forall v\in V\setminus S:D(v)=\min_{u\in S}\{d(u)+\ell(u,v)\}。就像 Dijkstra 算法，最初 S=\{s\} 且 D(s)=d(s)=0 且 \forall v\ne s:D(v)=\ell(s,v)。我们还从其继承了只有当 D(v)=d(v) 时我们才能访问一个节点 v\notin S 的约定。访问 v 意味着 v 会加入 S 并对于所有 (v,w)\in E,w\notin S，松弛 D(w)=\min\{D(w),D(v)+\ell(v,w)\}。对于 Dijkstra 算法，我们有：

引理 1 \quad%Eznibuil 如果 v\in V\setminus S 有最小 D(v)，则 D(v)=d(v)。

证明 \quad%Eznibuil 令 u 为在 s,v 最短路上第一个在 S 外的节点，则根据 S 的定义有 D(u)=d(u)，从而我们有 D(v)\ge d(v)\ge d(u)=D(u)\ge D(v)，蕴涵 D(v)=d(v)。\square

然而，与 Dijkstra 的算法相反，我们可能会访问一个节点 v\notin S，它并不使 D(v) 最小。不过，我们从 Dijkstra 的算法中继承了以下额外的结果：

引理 2 \quad%Eznibuil \min D(V\setminus S)=\min d(V\setminus S) 单调不降。

证明 \quad%Eznibuil 如果 S=V，\min D(V\setminus S)=\min d(V\setminus S)=\min\varnothing=\infty。否则，存在一个 v\in V\setminus S 使 d(v) 最小。令 u 为在 s,v 最短路上第一个在 S 外的节点。则 D(u)=d(u) 且 d(u)\le d(v)。无论如何，v 具有最小的 d(v)，所以 d(u)=d(v)。从而，我们有 \min D(V\setminus S)\le D(u)=d(u)=\min d(V\setminus S)。另一方面，有 D(w)\ge d(w) 对于所有 w\in V，所以 \min D(V\setminus S)\ge\min d(V\setminus S)。因此我们有 \min D(V\setminus S)=\min d(V\setminus S)。现在，\min d(V\setminus S) 是单调不降的，因为 S 只会增大且 d(w) 对于任何 w\in V 不会改变。于是，我们在越来越小的集合上求恒常的 d 值的最小，给出 \min d(V\setminus S) 只能递增。\square

我们将让 \omega 表示字的长度。我们会记 \lfloor\frac x{2^i}\rfloor 为 x\gg i 以强调它可以简单地通过将 i 个最小有效位向右移出来计算。注意有 x\le y\Rarr x\gg i\le y\gg i 并且 x<y\Larr x\gg i<y\gg i。若 f 是定义在集合 X 的元素上的函数，我们用 f(X) 表示 \{f(x)|x\in X\}。我们还采用 \min\varnothing=\infty 的标准。我们定义“\gg”的优先级低于 “\min”“+”和“-”。比如说，若 W\subseteq V，\min D(W)\gg i-1=(\min\{D(w)|w\in W\})\gg(i-1)。

通过一个桶，我们指的是一个动态集合 B，其中的元素可以被插入和删除，并且我们可以从中挑出一个未指定的元素。每个操作都应该在常数时间内得到支持。例如，一个桶可以被实现为一个双链表，人们只需从头部插入和挑选元素。使用 RAM 的间接寻址，我们通常创建一个数组 B(1\dots l) 的桶。然后，我们可以在常数时间内从一个任意的桶 B(i) 中插入和提取元素。同时，在常数时间内，我们可以从任何桶中删除一个元素。

3.%Eznibuil 避开排序瓶颈

现在我们将简要说明如何避免排序瓶颈的问题。亦即，我们将讨论一些对于 D(v)=d(v) 的简单情况，其中可能 D(v)>\min D(V\setminus S)。由此产生的算法远非高效，但在随后的章节中，我们将递归地应用这些想法，以便实现 SSSP 问题的线性时间解决方案。

引理 3 \quad%Eznibuil 假设点集 V 分为不相交的子集 V_1,\dots,V_k，并且子集之间的所有边至少有 \delta 的长度。进一步假设对于一些 i，v\in V_i\setminus S，使得 D(v)=\min D(V_i\setminus S)\le\min D(V\setminus S)+\delta，则 d(v)=D(v)。

证明 \quad%Eznibuil 为了说明 d(v)=D(v)，让 u 是 S 外从 s 到 v 的最短路径上的第一个节点，那么根据 S 的定义，d(u)=D(u)。如果 u\in V_i，如引理 1 的证明，有 D(v)\ge d(v)\ge d(u)=D(u)\ge D(v)，意味着 d(u)=D(u)，正如所期望的那样。现在，假设 u\notin V_i。由于从 V\setminus V_i 到 V_i 的所有边的长度为 \delta，我们有 D(v)\ge d(v)\ge d(u)+\delta=D(u)+\delta。另一方面，D(u)+\delta\ge\min D(V\setminus S)+\delta\ge\min D(V_i\setminus S)=D(v)，所以我们得出结论，我们在任何地方都有相等。特别是，这使我们得到结论 d(v)=D(v)。\square

朝第一个简单的 SSSP 桶算法进发，假设 \delta=2^\alpha。则 \min D(V_i\setminus S)\le\min D(V\setminus S)+\delta 被蕴涵于 \min D(V_i\setminus S)\gg\alpha\le\min D(V\setminus S)\gg\alpha。在算法上，我们现在将把每个 i\in\{1,\dots,k\} 分桶，依据权值 \min D(V_i\setminus S)\gg\alpha。亦即，我们有个作为桶的数组 B，其中 i 属于桶 B(\min D(V_i\setminus S)\gg\alpha)。注意到 \min D(V\setminus S)\gg\alpha=\min_i(\min D(V_i\setminus S)\gg\alpha)。从而，如果 i 是在索引最小的非空桶中，则 \min D(V\setminus S)\gg\alpha=\min D(V_i\setminus S)\gg\alpha。在更多的算法实现上，假设 ix 被维护为 \le 一个非空桶的最小索引。如果 i\in B(ix) 且 v\in V_i\setminus S 最小化了 D(v)，有 D(v)=\min D(V_i\setminus S)\le\min D(V\setminus S)+\delta，所以 D(v)=d(v) 因为引理 3，因此 v 可以被访问。

对于 ix 的维护，回顾一下，根据引理 2，\min D(V\setminus S) 是不降的。从而 \min D(V\setminus S)\gg\alpha 不降，所以永远不会降低 ix。另外，注意 D(v)<\infty 意味着 G 中存在一条从 s 到 v 的长度为 D(v) 的路径，因此 D(v)\le\sum_{e\in E}\ell(e)。于是，任何非空桶的最大索引 <\infty，被 \Delta=\sum_{e\in E}\ell(e)\gg\alpha 所约束。也就是说，所使用的桶索引只有 0,\dots,\Delta,\infty。将 \infty 视作 \Delta 的后驱，我们只需要大小为 \Delta+2 的数组作为桶。

基于上述讨论，我们得到以下 SSSP 算法。

算法 A \;%Eznibuil 解决 SSSP 问题，其中 V 被划分为子集 V_1,\dots,V_k，子集之间的所有边至少有 2^\alpha 的长度。

上述算法的复杂度为 O(m+\Delta) 加上为每个 i 维护 \min D(V_i\setminus S) 的成本。后者基本上将被递归地完成，且 \Delta=\sum_{e\in E}\ell(e)\gg\alpha 会保持较小通过选择较大的 \alpha。

4.%Eznibuil 连通分量的层状结构

我们现在要提出一个得出 D(v)=d(v) 的递归条件，这将在以后的线性时间 SSSP 算法中使用。它基于一个连通分量层状结构（component hierarchy），定义如下： 我们用 G_i 表示 G 的子图，其边集是来自 G 的边 e 满足 \ell(e)<2^i。接着，G_0 由单个节点组成。回顾一下，\omega 表示词的长度。从而，所有的权值都 <2^\omega，所以 G_\omega=G。在第 i 层连通分量层状结构上，我们有所有的 G_i 的连通分量（最大连通子图）。第 i 层中包含 v 的连通分量被表示为 [v]_i。[v]_i 的儿子们是连通分量 [w]_{i-1} 满足 [w]_i=[v]_i，亦即，w\in[v]_i。

引理 4 \quad%Eznibuil 如果 [v]_i\ne[w]_i，则 dist(v,w)\ge2^i。

证明 \quad%Eznibuil 因为 [v]_i\ne[w]_i，任何从 v 到 w 的路径必然包含一个 \ge2^i 的边。\square

通过 [v]_i^-，我们将用其表示 [v]_i\setminus S，注意 [v]_i^- 可能不连通。我们称 [v]_i 是 [v]_{i+1} 的一个最小儿子，如果 \min D([v]_i^-)\gg i=\min D([v]_{i+1}^-)\gg i（原文在 \min 之后多打了 (）。我们称 [v]_i 最小如果 [v]_i^-\ne\varnothing 且对于 j=i,\dots,b-1（原文如此，疑似 b 为 \omega），[v]_j 是 [v]_{j+1} 的最小儿子。只有当 V=S 时，要求 [v]_i\ne\varnothing 才有意义。如果 V=S，\min D([v]_i^-)=\infty 对于所有 [v]_i，因此在没有 [v]_i^-\ne\varnothing 的条件下所有 [v]_i 都是最小的；现在，没有 [v]_i 是最小的，如果 V=S。

在之后的引理 8，我们会展示 D(v)=d(v) 如果 [v]_0 是最小的。如果 v\in V\setminus S 最小化了 D(v)，就像 Dijkstra 算法中，\forall i:\min D([v]_i^-)\gg i=\min D([v]_{i+1}^-)\gg i=D(v)\gg i，所以 [v]_0 是最小的。关键点在于即使 D(v) 并非最小，[v]_0 仍然可能是最小的，于是为 D(v)=d(v) 给了我们一个比在 Dijkstra 算法中的更通用的条件。

引理 6 \quad%Eznibuil 假设 v\notin S 且 s 到 v 的最短路上第一个在 S 外的节点为 u 属于 [v]_i。则 d(v)\ge\min D([v]_i^-)。

证明 \quad%Eznibuil 因为 u 是我们的路径上第一个在 S 外的节点，所以 D(u) 是一个长度的下界，亦即 D(u)\le d(v)。更多的，因为 u\in[v]_i^-（原文为 [v]^-），所以 D(u)\ge\min D([v]_i^-)。\square

引理 7 \quad%Eznibuil 假设 v\notin S 且 [v]_{i+1} 是最小的，如果没有通向 v 的最短路径使得第一个在 S 外的节点属于 [v]_i，d(v)\gg i>\min D([v]_{i+1}^-)\gg i。

证明 \quad%Eznibuil 在所有通往 v 的最短路径中，挑选一个 P，使 S 外的第一个节点 u 在 [v]_k 中，且 k 最小。接着就有 k>i 且 d(v)=\ell(P)=D(u)+dist(u,v)。

我们通过对 \omega-i 的归纳来证明该引理的陈述。如果 u\notin[v]_{i+1}，我们有 i+1<\omega 且 [v]_{i+1} 的最小性蕴涵 [v]_{i+2} 的最小性。从而，根据归纳，d(v)\gg i+1>\min D([v]_{i+2}^-)\gg i+1。通过 [v]_{i+1} 的最小性，\min D([v]_{i+2}^-)\gg i+1=\min D([v]_{i+1}^-)\gg i+1。于是，d(v)\gg i+1>\min D([v]_{i+1}^-)\gg i+1，蕴涵 d(v)\gg i>\min D([v]_{i+1}^-)\gg i。

如果 u\in[v]_{i+1}^-，D(u)\gg i\ge\min D([v]_{i+1}^-)\gg i。更多的，因为 u\notin[v]_i，根据引理 4，dist(u,v)\ge2^i。因此，d(v)\gg i=(D(u)+dist(u,v))\gg i\ge(\min D([v]_{i+1}^-)\gg i)+1。\square

我们现在可以证明，[v]_0 的最小化意味着 D(v)=d(v)：

引理 8 \quad%Eznibuil 如果 v\notin S 且 [v]_i 是最小的，\min D([v]_i^-)=\min d([v]_i^-)。特别的，D(v)=d(v) 如果 [v]_0=\{v\} 是最小的。

证明 \quad%Eznibuil 因为对于所有 w 有 D(w)\ge d(w)，\min D([v]_i^-)\ge\min d([v]_i^-)。将 v 视为 [v]_i 中的一个任意节点，剩下的就是证明 d(v)\ge\min D([v]_i^-)。

在所有通往 v 的最短路径中，挑选一个 P，使 S 外的第一个节点 u 在 [v]_i 中，如果可能的话。如果 u\in[v]_i，引理 6 将直接给出结果。如果 u\notin[v]_i，根据引理 7，d(v)\gg i>\min D([v]_{i+1}^-)\gg i。然而，[v]_i 是 [v]_{i+1} 的最小儿子，所以 \min D([v]_{i+1}^-)\gg i=\min D([v]_i^-)\gg i。从而，d(v)\gg i>\min D([v]_i^-)\gg i，蕴涵 d(v)>\min D([v]_i^-)。\square

上面的定理给了我们访问节点的基本条件，把它们移到 S 中。我们的算法还需要引理 6 和引理 7 的一个结果。

引理 9 \quad%Eznibuil 如果 v\notin S 且 [v]_i 不是最小的但 [v]_{i+1} 是最小的，则 \min d([v]_i^-)\gg i>\min D([v]_{i+1}^-)\gg i。

证明 \quad%Eznibuil 考虑任何 w\in[v]_i^-。如果没有通往 w 的最短路径使得 S 之外的第一个节点在 [v]_i 中，则 \min d([v]_i^-)\gg i>\min D([v]_{i+1}^-)\gg i 直接从引理 7 得出。否则，根据引理 6，d(w)\ge\min D([v]_i^-)。更多的，[v]_i 的非最小性蕴涵 \min D([v]_i^-)\gg i>\min D([v]_{i+1}^-)\gg i。因此，我们得到了 d(w)\gg i>\min D([v]_{i+1}^-)\gg i 对于所有 w\in[v]_i^-，正如所期望的那样。\square

5.%Eznibuil 访问最小的一些节点

在本节中，我们将讨论当 [v]_0 最小时访问节点 v 的基本机制（原文为 dynamics）。首先，我们会展示一系列的引理，最后是引理 13，说明如果 [v]_i 曾经是最小的，那么在未来所有的时间里，\min D([v]_i^-)\gg i=\min d([v]_i^-)\gg i。在此基础上，我们将提出一个抽象的 SSSP 算法，显示我们在以后的线性时间算法中想要访问 G 的节点的基本顺序。

定义 1 \quad%Eznibuil 在本论文剩下的部分中，访问一个节点 v 意味着 [v]_0=\{v\} 是最小的。当 v 被访问了，会将它移入 S，并对于所有 (v,w)\in E 将 D(w) 赋值为 \min\{D(w),D(v)+\ell(v,w)\}。

注意，由于引理 8，无论何时访问 v 都意味着 D(v)=d(v)。

引理 10 \quad%Eznibuil 对于所有 [v]_i，\max d([v]_i\setminus[v]_i^-)\gg i-1\le\min d([v]_i^-)\gg i-1。

证明 \quad%Eznibuil 由于 d 是一个常函数，只需表明，在 w\in[v]_i^- 被访问稍前，d(w)\gg i-1=\min d([v]_i^-)\gg i-1。根据定义，在访问稍前 [w]_0 是最小的，所以通过引理 5，D(w)\gg i-1=\min D([w]_0^-)\gg i-1=\min D([w]_i^-)\gg i-1。另一方面，通过引理 8，D(w)=d(w) 且 \min D([w]_i^-)=\min d([w]_i^-)，所以我们得到了 d(w)\gg i-1=\min d([v]_i^-)\gg i-1，正如所期望的那样。\square

在下文中，我们将经常研究访问某个节点的事件之前和之后的情况。我们将使用符号 \lang e\rang^b（b 代表“before”）和 \lang e\rang^a（a 代表“after”）来表示表达式 e 应该在事件之前和之后被求值。根据引理 10，如果 j\ge i-1，\lang \min d([v]_i^-)\gg j\rang^a\ge\lang \min d([v]_i^-)\gg j\rang^b。从而，因为 \forall w:D(w)\ge d(w)，

引理 11 \quad%Eznibuil 假设 \min D([v]_i^-)\gg i=\min d([v]_i^-)\gg i 且访问一个节点 w\in V\setminus S 改变了 \min D([v]_i^-)\gg i。则 w\in[v]_i 且若 [v]_i^- 未变空，变化会导致 \min D([v]_i^-)\gg i 增加一。

证明 \quad%Eznibuil 我们研究的是访问节点 w 的事件。根据假定，\lang\min D([v]_i^-)\gg i\rang^b=\lang\min d([v]_i^-)\gg i\rang^b（原文将第一个 [v]_i^- 错写为 (v]_i^-）。从而，通过 (1)，\lang \min D([v]_i^-)\gg i\rang^a\ge\lang\min D([v]_i^-)\gg i\rang^b。根据假定，\lang\min D([v]_i^-)\gg i\rang^a\ne\lang\min D([v]_i^-)\gg i\rang^b，所以 \lang\min D([v]_i^-)\gg i\rang^a>\lang\min D([v]_i^-)\gg i\rang^b。因为 D 值从不增加，我们得到 \lang[v]_i^-\rang^a\subset\lang[v]_i^-\rang^b；因此 w\in\lang[v]_i^-\rang^b 且 \lang[v]_i^-\rang^a=\lang[v]_i^-\rang^b\setminus\{w\}。

假设 \lang[v]_i^-\rang^a 非空。因为 [v]_i 是连通的，必然存在一条边 (u,x) 在 [v]_i 中满足 u\notin\lang[v]_i^-\rang^a 且 x\in\lang[v]_i^-\rang^a。我们现在要论证的是

（原文错将 \min 置于 \lang\rang^b 外。）

如果 u\notin\lang[v]_i^-\rang^b，(2) 由引理 10 得出。否则，u=w。根据引理 8 和引理 5，[u]_0=[w]_0 的最小性蕴涵 d(u)\gg i=D(u)\gg i=\lang\min D([v]_i^-)\gg i\rang^b。于是，得到 (2)。

基于 (2)，由于 \ell(u,x)<2^i，我们得到

关于引理 11，应该注意的是，对于有向图，增加的幅度可能超过一。在本论文中，这是我们第一次使用无向性。

引理 12 \quad%Eznibuil 如果 [v]_i 是最小的，它会保持最小直到 \min D([v]_i^-)\gg i 增加，同时 \min d([v]_i^-)\gg i 也会增加。

证明 \quad%Eznibuil 假设 [v]_i 是最小的，但是访问一些节点 w 阻止了 [v]_i 保持最小。如果 w 是 S 中的最后一个节点，则会使 \min D([v]_i^-)\gg i 和 \min d([v]_i^-)\gg i 同时增加到 \infty。否则，某些 [v]_i 的祖先是最小的，我们取最小的 j 使 [v]_{j+1} 最小。更多的，我们取 u\in[v]_{j+1}^- 满足 [u]_j 是 [v]_{j+1} 的最小儿子。因此，当 [v]_j 不是最小时 [u]_j 是最小的。

在访问 w 之前，[v]_i 是最小的，所以 \lang\min D([v]_i^-)\gg j\rang^b=\lang\min D([v]_{j+1}^-)\gg j\rang^b 根据引理 5。同时，[v]_{j+1} 是最小的，通过引理 8 和 (1)，有 \lang\min D([v]_{j+1}^-)\gg j\rang^a\ge\lang\min D([v]_{j+1}^-)\gg j\rang^b。

在访问 w 之后，因为 [v]_{j+1} 是最小的且 [v]_j 不是 [v]_{j+1} 的最小儿子，根据引理 9，\lang\min d([v]_j^-)\gg j\rang^a>\lang\min D([v]_{j+1}^-)\gg j\rang^a。于是

（原文未打证明结束标记 \square。）

引理 13 \quad%Eznibuil 一旦 [v]_i 是最小的，在以后的所有时刻，

证明 \quad%Eznibuil 第一次 [v]_i 成为最小时，(3) 得到满足根据引理 8。现在，假设 (3) 在访问某些节点 w 前满足。因为 \forall u:D(u)\ge d(u)，(3) 只有通过增加 \min D([v]_i^-) 才能被违反。如果 \min D([v]_i^-)\gg i 增加了，根据引理 11，w\in[v]_i 且增加了一。访问 w 蕴涵 [w]_0 最小，从而 [w]_i=[v]_i 是最小的。如果 [v]_i 在访问后是最小的，(3) 由引理 8 得出。同时，如果 [v]_i^- 变空了，(3) 由 \min D([v]_i^-)\gg i=\min d([v]_i^-)\gg i=\infty 得出。如果 [v]_i 变为不是最小的且 [v]_i^- 不空，根据引理 12，\min d([v]_i^-)\gg i 也增加了。因为 \min d([v]_i^-)\gg i\le\min D([v]_i^-)\gg i 且 \min D([v]_i^-)\gg i 增加了一，我们得到 (3) 被恢复。\square

我们现在已经准备好在连通分量层状结构的基础上推导出一个无向 SSSP 问题的算法。该算法到目前为止是低效的，但它显示了我们打算在以后的线性时间算法中访问节点的顺序。作为我们的主要程序，我们有：

算法 B \;%Eznibuil SSSP，给定一个输入图 G=(V,E) 带有权值函数 \ell 和源点 s。它输出 D 满足 D(v)=d(v)=dist(s,v) 对于所有 v\in V。

现在提出一个访问最小连通分量 [v]_i 的递归程序。目标是访问所有 w\in[v]_i^- 满足 d(w)\gg i 等于 \min D([v]_i^-)\gg i 的调用时的值。根据引理 13，[v]_i 的调用时最小化意味着我们在整个调用过程中保持 \min D([v]_i^-)\gg i=\min d([v]_i^-)\gg i。因此，\min D([v]_i^-)\gg i 不会增加，直到我们访问了最后一个节点 w，d(w)\gg i 等于 \min D([v]_i^-)\gg i 的调用时的值。根据引理 12，这又意味着 [v]_i 将保持最小，直到我们访问了我们想要访问的最后一个节点。我们将维护一个索引 ix([v]_i)，它本质上等于 \min D([v]_i^-)\gg i-1。接着，一个 [v]_i 的儿子 [w]_{i-1} 是最小的如果 \min D([w]_{i-1}^-)\gg i-1=ix([v]_i)。从而，递归地，我们可以访问所有的节点 z\in[w]_{i-1}^- 满足 d(z)\gg i-1=\min D([w]_{i-1}^-)\gg i-1。因为 \min D([w]_{i-1}^-)\gg i-1=ix([v]_i)=\min D([v]_i^-)\gg i-1，d(z)\gg i=\min D([v]_i^-)\gg i-1，如所期望的。最后，当 ix([v]_i)\gg1=D([v]_i^-)\gg i 增加时，[v]_i 的访问就完成。以伪代码形式化，我们得到

算法 C \;%Eznibuil \textit{Visit}([v]_i) 假定 [v]_i 是最小的。它访问的所有 w\in[v]_i^- 满足 d(w)\gg i 等于调用时 \min D([v]_i^-)\gg i 的值。

正确性 \quad%Eznibuil 我们现在证明算法 C 是正确的，也就是说，如果 [v]_i 是最小的，\textrm{Visit}([v]_i) 访问的节点 w\in[v]_i^- 的 d(w)\gg i 等于调用时 \min D([v]_i^-)\gg i 的值。证明方法是通过对 i 的归纳。

如果 i=0，我们直接在步骤 \text{C.1} 访问 v。通过引理 8，D(v)=d(v)。从而，d(v)\gg i 等于调用时 \min D([v]_i^-)\gg i=D(v)\gg i 的值，如所期望的。在访问 v 之后，[v]_i^-=\varnothing，所以我们完成了。

现在，假设 i>0。归纳地，如果一个子调用 \text{Visit}([w]_{i-1})（步骤 \text{C.3.1.2}）是在 [w]_{i-1} 最小的情况下进行的，我们可以假设它正确地访问了所有 u\in[w]_{i-1}^-，而 d(u)\gg i-1 等于子调用调用时 \min D([w]_{i-1}^-)\gg i-1 的值。我们将证明当 [v]_i^-\ne\varnothing 时的以下不变量：

当 ix([v]_i) 在步骤 \text{C.2} 中被首次赋值，它被赋值为了 \min D([v]_i^-)\gg i-1。而且，在那时，[v]_i 是最小的，所以 \min D([v]_i^-)=\min d([v]_i^-) 根据引理 8。于是 ix([v]_i)=\min D([v]_i^-)\gg i-1=\min d([v]_i^-)\gg i-1，同时蕴涵 (4) 和 (5)。现在，假设 (4) 和 (5) 在循环 \text{C.3} 的一个迭代开始时都成立。

引理 14 \quad%Eznibuil 如果 \min D([v]_i^-)\gg i 没有增加，[v]_i 保持最小且 (4) 和 (5) 保持成立。

证明 \quad%Eznibuil 根据引理 12 和引理 8，[v]_i 保持最小且 \min D([v]_i^-)=\min d([v]_i^-)。接着，根据 (1)，\min D([v]_i^-)\gg i-1 是不降的，所以违反 (5) 的情况应该是由于 ix([v]_i)。但是，ix([v]_i) 在步骤 \text{C.3.2} 只会增加，只有 \forall[w]_{i-1}\subseteq[v]_i:\min D([w]_{i-1}^-)\gg i-1\ne ix([v]_i) 时会进入。特别的，在增加之前，ix([v]_i)\ne\min D([v]_i^-)\gg i-1=\min_{[w]_{i-1}\subseteq[v]_i}(\min D([w]_{i-1}^-)\gg i-1)。更多的，根据 (5)，ix([v]_i)\le\min D([v]_i^-)\gg i-1。因此，ix([v]_i)<\min D([v]_i^-)\gg i-1=\min d([v]_i^-)\gg i-1，所以 ix([v]_i) 的增加一并不能违反 (5)。更多的，因为 \min D([v]_i^-)\gg i 没有增加且 \min D([v]_i^-)=\min d([v]_i^-)，(5) 意味着 (4) 得到了保留。\square

引理 15 \quad%Eznibuil 如果子调用 \text{Visit}([w]_{i-1})（步骤 \text{C.3.1.2}）在 \min D([v]_i^-)\gg i 增加前被调用，所有访问过的节点 u 满足 d(u)\gg i 等于 \min D([v]_i^-)\gg i 的原始值（为 \text{Visit}([v]_i) 内的访问所要求的）。

证明 \quad%Eznibuil 根据假设，当调用子调用 \text{Visit}([w]_{i-1}) 时，引理 14 适用，所以 (4) 和 (5) 成立。\text{C.3.1.1} 的赋值意味着 ix([v]_i)=\min D([w]_{i-1}^-)\gg i-1，显然，\min D([w]_{i-1}^- )\gg i-1\ge\min D([v]_i^-)\gg i-1\ge\min d([v]_i^-)\gg i-1。那么 (5) 意味着到处都是相等的，所以 \min D([w]_{i-1}^-)\gg i-1=\min D([v]_i^-)\gg i-1，因此 [w]_{i-1} 继承了 [v]_i 的最小性。从而，通过归纳，\text{Visit}([w]_{i-1}) 正确访问了节点 u\in[w]_i^- 且 d(u)\gg i-1 等于子调用时的 \min D([w]_{i-1}^-)\gg i-1 的值。然而，在子调用时，\min D([w]_{i-1}^-)\gg i-1=ix([v]_i)，根据 (4)，ix([v]_i)\gg1=\min D([v]_i^-)\gg i，所以 d(u)\gg i=\min D([v]_i^-)\gg i。\square

引理 16 \quad%Eznibuil 当循环 \text{C.3} 终止时，\min D([v]_i^-)\gg i 已经增加。

证明 \quad%Eznibuil 如果 \min D([v]_i^-)\gg i 没有增加，根据引理 14，(5) 成立，且 (5) 意味着 ix([v]_i)\gg1\le\min D([v]_i^-)\gg i。最初，我们通过 (4) 得到了相等。但是，只有当 ix([v]_i)\gg1 增加或 [v]_i^- 成为空时，循环才能终止，设定 \min D([v]_i^-)\gg i=\infty。\square

到目前为止，我们将只是假设终止，把终止的证明推迟到下一节的效率证明中。因此，根据引理 16，\min D([v]_i^-)\gg i 最终会增加。令 \text{Visit}([w]_{i-1}) 为发生增加的子调用。

根据引理 13，\min d([v]_i^-)\gg i 随着 \min D([v]_i^-)\gg i 的增加而增加。因此，根据引理 15，\text{Visit}([w]_i) 将不再访问更多的节点。此外，这意味着我们已经访问了所有节点 u\in[v]_i，d(u)\gg i 等于 \min D([v]_i^-) 的原始值，所以我们现在已经访问了所有节点 u\in[v]_i，d(u)\gg i 等于 \min D([v]_i^-) 的原始值，所以我们现在完全访问了所需的节点。

因为 \min d([v]_i^-)\gg i 增加了且 \forall[w]_{i-1}\subseteq[v]_i:\min D([w]_{i-1}^-)\gg i-1\ge\min D([v]_i^-)\gg i-1\ge\min d([v]_i^-)\gg i-1，ix([v]_i) 现在将只是递增，而没有递归子调用 \text{Visit}([w]_{i-1})，直到 [v]_i^- 被清空，或者 ix([v]_i)\gg1 被增加一。

由于在增加 \min D([v]_i^-)\gg i 之后没有更多的节点被访问，根据引理 11，增加了一。从而，我们得出结论，所有的 ix([v]_i)、D([v]_i^-)\gg i 和 \min d([v]_i^-)\gg i 都增加了一，恢复了 (4) 的等式。由于 ix([v]_i) 现在有最小的值，使得 ix([v]_i)\gg1=\min d([v]_i^-)\gg i，我们得出结论，(5) 也被满足。

根据引理 13，在未来所有时刻 \min d([v]_i^-)\gg i=\min D([v]_i^-)\gg i。此外，ix([v]_i) 和 \min d([v]_i^-) 只能在调用 \text{Visit}([v]_i) 时发生变化，因此我们得出结论，(4) 和 (5) 将保持满足，直到下一次这样的调用。这就完成了证明算法 C 是正确的。\LARGE\diamond

6.%Eznibuil 走向线性时间算法

在本节中，我们会介绍线性时间 SSSP 算法的构成。

6.1 连通分量树 \quad%Eznibuil 定义连通分量树 \mathscr T 代表连通分量层状结构，跳过所有节点 [v]_i=[v]_{i-1}。因此，\mathscr T 的叶子是单节点连通分量 [v]_0=\{v\},v\in V。内部节点是连通分量 [v]_i,i>0,[v]_{i-1}\subset[v]_i。\mathscr T 中的根是节点 [v]_r=G，其 r 最小。节点 [v]_i 的父亲是其在连通分量层状结构中最近的度 \ge2 的祖先。由于 \mathscr T 没有度为一的节点，所以节点的数量是 \le 2n-1。在第 7 节，我们展示了如何在 O(m) 时间内构建 \mathscr T。考虑到 \mathscr T，我们可以直接修改算法 C 中 \text{Visit} 的实现，使其在 \mathscr T 内递归，从而跳过连通分量层状结构中不在 \mathscr T 内的连通分量。在本文的其余部分，当我们谈论儿子或父亲时，可以理解为我们指的是 \mathscr T 而不是连通分量层状结构。[v]_i 的最小儿子 [w]_h 最小化了 \min D([w]_h^-)\gg i-1。因此，当且仅当 \mathscr T 的一个连通分量在连通分量层状结构中对 \mathscr T 来说是最小的，它就是最小的。

6.2 一个线性空间的桶状结构 \quad%Eznibuil 我们说一个连通分量 [v]_i\in\mathscr T 在第一次调用 \text{Visit}([v]_i) 时被访问。现在的想法是，对于每个被访问的连通分量 [v]_i，我们将根据 \min D([w]_h^-)\gg i-1 将儿子 [w]_h 放入桶。也就是，[w]_h 是在一个桶中存在，该桶表示为 B([v]_i,\min D([w]_h^-)\gg i-1)。因为算法 C 中有 ix([v]_i)=\min D([v]_i^-)\gg i-1，那么在 B([v]_i,ix([v]_i)) 中很容易找到 [v]_i 的最小儿子。

关于一个被访问的连通分量 [v]_i 的桶状结构，我们可以再次使用索引 ix([v]_i)，对于如果 [v]_i 有父亲 [v]_j 在 \mathscr T 中，[v]_i 属于 B([v]_j,ix([v]_i)\gg j-i)=B([v]_j,\min D([v]_i^-)\gg j-1)。被访问连通分量的未被访问儿子分桶被推迟到以后进行。在本小节的其余部分，重点是表明我们可以有效地将 B(\cdot,\cdot) 中的所有“相关”桶嵌入一个具有 O(m) 项的数组 A 中。

引理 17 \quad%Eznibuil 如果 [w]_h 是 [v]_i（原文误为 v_i）的一个最小儿子，\min d([v]_i)\gg i-1\le\min D([w]_h^-)\gg i-1\le\max d([v]_i)\gg i-1。

证明 \quad%Eznibuil 根据引理 8，\min D([w]_h^-)=\min d([w]_h^-)，且根据最小性的定义，[w]_h^- 是 [v]_i 的非空子集。\square

令 ix_0([v]_i) 表示 \min d([v]_i)\gg i-1。我们会计算一些 ix_\infty\ge\max d([v]_i)\gg i-1。接着，根据引理 17，任何属于 [v]_i 的最小儿子应该在 B([v]_i,ix_0([v]_i)\cdots ix_\infty([v]_i)) 中被找到。反之，如果 \min D([w]_h^-)\gg i-1\notin\{ix_0([v]_i),\dots,ix_\infty([v]_i)\}，我们知道 [w]_h 不是最小的，因此没有必要将 [w]_h 放入 B([v]_i,\cdot)。我们于是定义 B([v]_i,q) 是相关的当且仅当 ix_0([v]_i)\le q\le ix_\infty([v]_i)。

注意到 [v]_i 的直径被 \sum_{e\in[v]_i}\ell(e) 所约束。这立即推出 \max d([v]_i)\le\min d([v]_i)+\sum_{e\in[v]_i}\ell(e)。定义 \Delta([v]_i)=\lceil\sum_{e\in[v]_i}\ell(e)/2^{i-1}\rceil 以及 ix_\infty([v]_i)=ix_0([v]_i)+\Delta([v]_i)。然后，\max d([v]_i)\gg i-1\le ix_\infty([v]_i)，如所期望的那样。

引理 18 \quad%Eznibuil 相关的桶的总数 <4m+4n。

证明 \quad%Eznibuil 与 [v]_i 联系起来，我们有 \Delta([v]_i)+1\le2+\sum_{e\in[v]_i}\ell(e)/2^{i-1} 数量的相关桶。因为 \mathscr T 是一个具有 n 个节点的有根树，满足所有的非叶子节点都有至少两个儿子，所以 \mathscr T 中的 [v]_i 数量 \le2n-1。于是，相关的桶的总数至多是

现在，考虑任何 e=(u,w)\in E。令 j=\lfloor\log_2\ell(e)\rfloor+1。接着 e\in[v]_i\Lrarr i\ge j\land[v]_i=[u]_i。因为 \ell(e)<2^j，我们得到：

于是，相关的桶的总数 <4m+4n。\square

现在我们将展示如何有效地将 B(\cdot,\cdot) 的相关桶嵌入到一个具有索引集 {0,\dots,N}，其中 N=O(m) 是相关桶的总数。

命题 27 \quad%Eznibuil 假设连通分量树 \mathscr T 已经被计算出来（参见第 7 节），并假设有一个神迹，可以在线性总时间内动态维护 \mathscr U 中每个根 [v]_i 的 \min D([v]_i^-) 的变化值（参见第 8 节）。那么解决 SSSP 问题就不需要超过 O(m) 的时间和空间。

证明 \quad%Eznibuil 除了桶，空间上界是微不足道的。引理 18 说我们只有 O(m) 个相关的桶，所以从我们在桶数组 A 中对这些桶的线性实现来看，我们得出结论，只需要 O(m) 的空间。

显然，\text{Visit}(v)（算法 E）花费的总时间是 O(m)。在 \text{Expand}([v]_i)（算法 D）中花费的时间与 B([v]_i,\cdot) 中相关桶的数量成正比，所以根据引理 18，\text{Expand} 中花费的总时间是 O(m)。

在考虑了 \text{Visit}(v)（算法 E）所花费的时间后，\text{Visit}([v]_i)（算法 F）所花费的时间是通过 ix([v]_i) 的增加来均摊掉的，或清空 [v]_i^-。由于 B([v]_i,ix([v]_i)) 总是一个相关桶，根据引理 18，ix([v]_i) 最多可以有 O(m) 的增加。另外，每个 [v]_i^- 只被清空一次，所以后一个事件只能发生 O(n) 次。

根据 \text{Visit}([v]_i) 的正确性，要么 [v]_i^- 被清空，要么 ix([v]_i)\gg j-i=\min D([v]_i^-)\gg j-1 增加。后者意味着 ix([v]_i) 增加了，所以我们得出结论，在任何一种情况下，调用 \text{Visit}([v]_i) 都是被支付了的。

重复循环的每一次迭代，即步骤 \text{F.3}，都是通过增加 ix([v]_i) 或清空 [v]_i^- 来支付的，这很平凡。最后，步骤 \text{F.3.1} 中 while 循环的每一次迭代都由调用 \text{Visit}([w]_h) 来支付。\square

7.%Eznibuil 连通分量树

在这一节中，我们将为上一节中定义的连通分量树 \mathscr T 提出一个线性时间和空间构造。回顾一下，在第 i 层，我们希望得到所有权重 <2^i 的边。因此，我们只对权重的最重要位（msb）的位置感兴趣，即 msb(x)=\lfloor\log_2x\rfloor。虽然 msb 并不总是直接可用的，但它可以通过三个标准的 \text{AC}^0 操作获得，首先将整数 x 转换为双精度浮点，然后通过两次移位提取指数。另外，msb 可以通过恒定数量的乘法来编码，如 Fredman 和 Willard [1993] 所述。

我们的第一步是构建一个最小生成树 M。如 Fredman 和 Willard [1994] 所述，这可以在线性时间内确定性地完成。对于 G_i，令 M_i=(V,\{e\in M|\ell(e)<2^i\})。还有，令 [v]_i^M 表示在 M_i 中 v 的连通分量。显然 [v]_i^M 是 [v]_i 的生成树，所以，M_i 中的这些连通分量与 G_i 中的在节点上是相同的。以及，由于 [v]_i^M 是 [v]_i 的生成树，

因此 \sum_{e\in[v]_i^M}\ell(e) 给了我们一个比 \sum_{e\in[v]_i}\ell(e) 更好的 [v]_i 直径的上界。我们可以然后重新定义第 6 节的 \Delta 为 \Delta([v]_i)=\lceil\sum_{e\in[v]_i^M}\ell(e)/2^{i-1}\rceil。

注意因为 M 只有 n-1 条边，引理 18 指出，我们只有 4(n-1)+4n<8n 个相关桶。因此，命题 27 证明中的大多数界限都从 O(m) 减少到 O(n)。更确切地说，我们在 \text{Visit}(v)（算法 E）中仍然花费了 O(m) 的总时间，但除去这些调用，在 \text{Expand}([v]_i)（算法 D）和 \text{Visit}([v]_i)（算法 D）中花费的总时间从 O(m) 减少到 O(n)。

使用 M 而不是 G 的主要动机是 M 是一棵树，Gabow 和 Tarjan [1985] 已经证明我们可以在线性时间和空间内预处理一棵树，从而支持以每次操作的常数成本进行联合查找操作。更确切地说，我们在一个动态子森林 S\subseteq M 上进行操作，从 S 由单节点组成开始。S 的每个组成部分都有一个典型节点，find(v) 返回 v 所属的 S 的组成部分的典型节点。因此，find(v)=find(w)，当且仅当 v 和 w 在 S 的同一个连通分量中。对于一条边 (v,w)\in M，union(v,w) 将 (v,w) 加入 S。新的连通分量的典型节点被假定为调用 union(v,w) 之前的 find(v) 或 find(w)。

现在让 e_1,\dots,e_{n-1} 是根据 msb(\ell(e_i)) 排序的 M 的边。注意，msb(\ell(e_i))<\log_2w。因此，如果 \log w=O(n)，这样的序列可以通过简单的分桶在线性时间内产生。否则，\log w=O(w/(\log n\log\log n))，然后我们可以通过打包合并在线性时间内进行排序 [Albers and Hagerup 1997; Andersson et al. 1995]。

定义 msb(\ell(e_0))=-1 以及 msb(\ell(e_n))=\omega，注意到

因此，对于 i=1,\dots,n-1，我们将依次调用 union(e_i)，如果 msb(\ell(e_i))<msb(\ell(e_{i+1}))，我们将为 \mathscr T 收集 S 的所有新连通分量。为了计算 \Delta 值，对于具有典型元素 v 的连通分量，我们存储 s(v) 等于跨越它的边的权值之和。为了有效地识别 \mathscr T 的新连通分量和它们的父亲指针，我们维护了自最后一个连通分量被收集以来，连通分量的旧典型元素的集合 X。现在，所需的算法是直截了当的。

算法 G \;%Eznibuil 从最小生成树 M 构建 \mathscr T 和 \Delta(\cdot)。\mathscr T 的一个叶子 [v]_0 被识别为 v，内部连通分量被识别为由自然数构成的一个初始段。如果 c 识别了 [v]_i\in\mathscr T，\wp(c) 表示 \mathscr T 中 [v]_i 的父亲的识别标识，\Delta(c)=\lceil\sum_{e\in[v]_i^M}\ell(e)/2^{i-1}\rceil。

（原文 \textbf{G.3.6.4.1.} 及 \textbf{G.4.} 行的 c 未正确使用斜体，\textbf{G.2.} 处误写为 c\gets0。）

综上所述，我们得到了，

命题 28 \quad%Eznibuil 连通分量树 \mathscr T 在 O(m) 的时间和空间内被计算了。

8.%Eznibuil 未访问数据的结构

在这一节中，我们将证明，对于连通分量树 \mathscr T 的未访问部分 \mathscr U 中的根 [v]_i 的变化集，我们可以在线性总时间内维护变化值 \min D([v]_i^-)。这是命题 27 的最后一个不合理的假设。因此，本节的结果将使我们能够以线性时间的 SSSP 算法作为结论。

首先，请注意，由于 \mathscr U 的每个根 [v]_i 是未被访问的，[v]^-=[v]_i。我们将 G 的每个节点 v 与 T 的叶子 [v]_0 相区别。我们想在摊销后的常数时间内支持的操作是：（1）如果 D(v) 对于某个未访问过的根 [v]_i 的节点 v 来说是减少的，则更新 \min D([v]_i)，以及（2）如果未访问过的根 [v]_i 被访问过，\mathscr T 中 [v]_i 的每个儿子 [w]_h 成为 \mathscr U 中的一个新根，所以我们需要找到 \min D([w]_h^-)。我们将把这个问题简化为一个稍微干净的数据结构问题。

让 v_1,\dots,v_n 是由 \mathscr T 的每个内部节点的儿子的任意排序所引起的 G 的顶点的排序。现在，对于 \mathscr U 中的每个根 [v]_i，[v]_i 的节点是 [v]_i 下的叶子，它们形成了 v_1,\dots,v_n 的一个连接段 v_j,\dots,v_l。我们希望维护 \min D([v]_i)=\min_{j\le k\le l}D(v_k)。当我们从 \mathscr U 中删除一个根时，我们把它的段分成子树的段。因此，我们研究的是将 v_1,\dots,v_n 动态分割成相连的段，对于每个段，我们想知道最小 D 值。当我们开始时，v_1,\dots,v_n 形成了一个段，并且 D(v_i)=\infty，对于所有的 i。我们现在可以重复（1）减少一些 v_i 的 D 值，或（2）分割一个片段。每次操作后，我们需要更新所有段的最小 D 值。每次分割都被认为是一分为二的分割，因为我们总是可以通过几个一分为二的分割来实现分割为 >2 个片段。请注意，对于一个长度为 n 的序列，我们最多可以有 n-1 次一分为二。

Gabow 已经展示了我们可以在 O(m\alpha(m,n)) 的总时间内容纳 n-1 次分裂和 m 次减少 [Gabow 1985, Sect.4]。然而，这里我们提出了一个 O(m+n) 的解决方案。我们的改进是基于原子堆 [Fredman and Willard 1994]。Gabow 的解决方案在指针机上工作，只比较权重，而原子堆则使用 RAM 的全部功能。作为我们的第一步，我们表明

引理 29 \quad%Eznibuil 对于一个长度为 n 的序列，我们可以容纳 \le n-1 次分裂和 m 次减少在 O(m+n\log n) 中。

证明 %Eznibuil 首先我们给 v_1,\dots,v_n 均匀地分为二叉型的区间。也就是说，最顶层是 v_1,\dots,v_n 且一个区间 v_i,\dots,v_j,j>i 有两个儿子 v_i,\dots,v_{\lfloor(i+j)/2\rfloor} 和 v_{\lfloor(i+j)/2\rfloor+1},\dots,v_j。

当一个区间不包含在一个区间内时，就被称为断裂，任何区间都是最多 2\log_2n 个最大的不断裂区间的连接。

在这个过程中，每个顶点都有一个指向它所属的最大不间断区间的指针，而每个最大不间断区间都有一个指向它所属的段的指针。对于每个区段和每个最大不间断区间，我们维护最小的 D 值。因此，当一个 D 值减少时，如果它低于包含它的最大不间断区间或包含它的段的当前最小 D 值，我们就相应地减少这个最小值，在常数时间内。

当一个区段被分割时，我们可能会打破一个区间，最多产生 2\log_2n 个新的最大不连续区间。对于这些不相交的区间中的每一个，我们访问它的所有顶点，以找到最小的 D 值，并将这些顶点的指针恢复到包含它们的新的较小的最大不间断区间。由于每个顶点都包含在 \log_2n 个区间中，这个过程的总成本是 O(n\log n)。接下来，对于这两个新区段中的每一个，我们找到最小的 D 值，即它们所连接的最多 2\log_2n 个最大不间断区间的最小 D 值。每次分割需要 O(\log n) 时间，因此总时间为 O(n\log n)。\square（译者注：亦即 OI 常说的线段树。）

为了降低到线性总成本，我们将对 Fredman 和 Willard 的原子堆进行复述 [Fredman and Willard 1994]。让 T(m,n,s) 表示容纳 m 个减少和 n-1 个分割的总成本，从一个长度为 n 的序列开始，该序列已经被分成最多长度为 s 的初始段。从引理 29 来，我们得到

（中间证明略，以后再来补翻译。）

命题 36 \quad%Eznibuil T(m,n,n)=O(m)。

证明 \quad%Eznibuil 以 i=2 应用引理 32，T(m,n,n)\le O(m)+T(m,n,\log\log n)。根据定义，T 在第三个参数上单调不增，所以 T(m,n,\log\log n)\le T(m,n,\sqrt[4]{\log n})。现在，结果可以直接由引理 35 得到。\square（译者注：讲道理，如果 \log\log n>\sqrt[4]{\log n}，则 n\in[6,2^{65536})。）

9.%Eznibuil 总结

结合命题 27、28 和 36，我们现在已经证明了

定理 37 \quad%Eznibuil 对于具有正整数权重的无向图的单源最短路径问题，有一个确定性的线性时间和线性空间算法。

对我们的线性时间和空间算法的反对意见可能是，它使用了 Fredman 和 Willard 的原子堆 [Fredman and Willard 1994]。正如 Fredman 和 Willard [1994] 所说，原子堆只在 n>2^{12^{20}} 的情况下定义。此外，原子堆还使用了乘法，这不是一个 \text{AC}^0 操作。正如 Andersson 等人 [1999] 所指出的，使用非 \text{AC}^0 运算并不是固有的。乘法可以被 \text{AC}^0 中一些简单的选择和复制操作所取代，而这些操作在标准指令集中只是缺失。这些量身定做的指令也会极大地减少常数。尽管如此，在今天的计算机上，看看没有原子堆我们能做得多好是有意义的。

我们新的无定向单源最短路径算法的主要工具是使用桶。我们现在要讨论的是，如果我们把自己限制在“基本算法”上，除了桶之外在指针机上运行，并且只使用标准的 \text{AC}^0 操作，我们能做得多好。特别是，我们将避免像在原子堆中那样进行花哨的跳表和位操纵。

我们的第一个问题是在第 7 节的最小生成树计算中，它取自 Fredman 和 Willard [1994]，是基于原子堆的。对于我们的算法来说，它满足与一个生成树，该生成树在图中是最小的，其中每个权重 x 被 msb(x)=\lfloor\log_2x\rfloor 取代（记得 msb 是用三个标准的 \text{AC}^0 操作找到的：首先转换为双精度浮点数，然后用两次移位提取指数）。使用简单的桶，我们可以在 O(\log C+m) 时间内根据边的 msb 权重对边进行平凡地排序，其中 C 是最大的边权重。在对 msb 权重进行预排序后，使用 Kruskal 的算法 [Kruskal 1956] 和 Tarjan 的 union-find 算法 [Tarjan 1975]，可以在 O(\alpha(m,n)m) 时间内找到 msb 最小生成树。为了达到 O(\alpha(m,n)m) 的时间界限，我们也可以在构造 \mathscr T 和 \Delta(\cdot) 时用 Tarjan 的 union-find 算法取代 Gabow 和 Tarjan [1985] 中基于表格的 union-find 算法。这甚至可以在用 Kruskal 算法构建生成树的过程中即时完成。

如果我们使用 Gabow 的 O(\alpha(m,n)m) 解决方案 [Gabow 1985, Sect. 4]，就可以避免第 8 节中原子堆的使用，该解决方案直接在指针机上工作。加起来，我们得出结论，我们有一个运行时间为 O(\log C+\alpha(m,n)m) 的 SSSP 问题的基本算法。

上述的 \log C 项源于在 msb 权重的桶排序中必须遍历 msb(C) 个桶。正如第 7 节所指出的，如果 \omega\ge m，msb 权重的排序可以通过打包合并在 O(m) 时间内完成 [Albers and Hagerup 1997; Andersson et al. 1995]。在今天的计算机上，\omega\ge n 其实并不重要，因为 \omega\le64。然而，打包合并本质上是将 RAM 作为一种带移位的矢量处理器，在未来具有巨大字长的处理器的情况下，它可能是相关的。此外，打包合并只使用标准的 \text{AC}^0 操作，所以我们的结论是

定理 38 \quad%Eznibuil 在具有标准 AC^0 指令的 RAM 上，对于具有正整数权重的无向图的单源最短路径问题，有一个确定性的 O(\alpha(m,n)m) 时间和线性空间的算法。

总之，对于具有正整数权重的无定向单源最短路径问题，已经提出了一个确定性的线性时间和线性空间算法。这种理论上的最优算法本身并不适合实施，但它有一些可实施的变体，在理论上和实践中都应该是很好的。

附录 A.%Eznibuil 浮点权重

（此处略。）

鸣谢 %Eznibuil 我要感谢 J. ACM. 的审稿人，他们提出了一些非常详尽和有用的意见。此外，我还要感谢 Stephen Alstrup 对第 8 节的材料进行了有价值的讨论，特别是他给我指出了 [Gabow 1985]。

参考文献

Ahuja, R. K., Melhorn, K., Orlin, J. B., and Tarjan, R. E. 1990. Faster algorithms for the shortest path problem. J. ACM 37, 213–223.

Albers, S. and Hagerup, T. 1997. Improved parallel integer sorting without concurrent writing. Inf. Control 136, 25–51.（1992 年的 Free access 版本。）

Andersson, A., Hagerup, T., Nilsson, S., and Raman, R. 1995. Sorting in linear time? In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29–June 1). ACM, New York, pp. 427–436.

Andersson, A. Miltersen, P. B. and Thorup, M. 1999. Fusion trees can be implemented with AC0 instructions only. Theoret. Comput. Sci., 215, 337–344.

Cherkassky, B. V., Goldberg, A. V., AND Silverstein, C. 1997. Buckets, heaps, lists, and monotone priority queues. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 83–92.

Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numer. Math. 1, 269–271.

Dinic, E. A. 1978. Finding shortest paths in a network. In Transportation Modeling Systems, Y. Popkov and B. Shmulyian, eds. Institute for System Studies, Moscow, CIS, pp. 36–44.

Fredman, M. L., and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (July), 596–615.

Fredman, M. L., and Willard, D. E. 1993. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424–436.

Fredman, M. L., and Willard, D. E. 1994. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 533–551.

Gabow, H. N. 1985. A scaling algorithm for weighted matching on general graphs. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 90–100.

Gabow, H. N. and Tarjan, R. E. 1985. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209–221.（1983 年的 Free access 版本。）

Henzinger, M. R., Klein, P., Rao, S., and Subramanian, S. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 53, 2–23.（作者不完全相同但名字相同的 1994 年的 Free access 版本。）

Kruskal, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48–50.

Melhorn, K., and Nähler, S. 1990. Bounded ordered dictionaries in O(log log n) time and O(n) space. Inf. Proc. Lett. 35, 183–189.

Raman, R. 1996. Priority queues: small monotone, and trans-dichotomous. In Proceedings of the 4th Annual European Symposium on Algorithms. Lecture Notes on Computer Science, vol. 1136, Springer-Verlag, New York, pp. 121–137.

Raman, R. 1997. Recent results on the single-source shortest paths problem. SICACT News 28, 81–87.

Tarjan, R. E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2 (Apr.), 215–225.

Thorup, M. 1996. On RAM priority queues. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 59–67.

Thorup, M. 1998. Floats, integers, and single source shortest paths. In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science. Lecture Notes on Computer Science, vol. 1373. Springer-Verlag, New York, pp. 14–24.

van Emde Boas, P. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6, 80–82.

van Emde Boas, P., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99–127.

Willard, D. E. 1992. Applications of the fusion tree method to computational geometry and searching. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 286–295.（原文误为“pp. 386–395”。）

Williams, J. W. J. 1964. Heapsort. Commun. ACM 7, 6 (June), 347–348.

1998 年 1 月收到；1998 年 11 月完成修订；1998 年 12 月通过。

2023.6.27 14:15 初稿完成，略去第 6、8 节的一些证明、附录 A 和参考文献。

2023.6.30 13:37 补上了参考文献。

2023.7.2 22:50 参考文献有 ACM Digital Library 的都附上了链接。Kruskal 的附上了 AMS 的链接。（肯定不会放 Google Scholar 的链接啊。）