A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
无向实权图单源最短路径的随机算法

Ran Duan $^{* 1}$ , Jiayi Mao $^{† 1}$ , Xinkai Shu $^{‡ 2}$ , and Longhui Yin $^{§ 1}$
Ran Duan $^{* 1}$ , Jiayi Mao $^{† 1}$ , Xinkai Shu $^{‡ 2}$ , 和 Longhui Yin $^{§ 1}$ $^{1}$ Institute for Interdisciplinary Information Sciences, Tsinghua University
$^{1}$ 清华大学跨学科信息科学研究院 $^{2}$ The University of Hong Kong
$^{2}$ 香港大学

October 5, 2023 2023 年 10 月 5 日

Abstract 摘要

In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O (m \sqrt{\log n \cdot \log \log n})$ in the comparison-addition model. This is the first algorithm to break the $O (m + n \log n)$ time bound for real-weighted sparse graphs by Dijkstra’s algorithm with Fibonacci heaps. Previous undirected non-negative SSSP algorithms give time bound of $O (m α (m, n) + min {n \log n, n \log \log r})$ in comparison-addition model, where $α$ is the inverse-Ackermann function and $r$ is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of $Ω (m + min {n \log n, n \log \log r})$ for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchy-based approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.
在具有真实非负权重的无向图中，我们提出了一种新的随机算法，用于单源最短路径（SSSP）问题，其在比较-加法模型中的运行时间为 $O (m \sqrt{\log n \cdot \log \log n})$ 。这是第一个突破 Dijkstra 算法与 Fibonacci 堆在真实权重稀疏图中 $O (m + n \log n)$ 时间界限的算法。之前的无向非负 SSSP 算法在比较-加法模型中给出的时间界限为 $O (m α (m, n) + min {n \log n, n \log \log r})$ ，其中 $α$ 是反阿克曼函数， $r$ 是最大边权重与最小边权重的比率[Pettie & Ramachandran 2005]，而在 RAM 模型中，对于整数边权重则是线性时间[Thorup 1999]。请注意，针对无向真实权重 SSSP 的基于层次的算法有一个提出的复杂度下界 $Ω (m + min {n \log n, n \log \log r})$ [Pettie & Ramachandran 2005]，但我们的算法不遵循该下界所需的属性。作为一种非基于层次的方法，我们的算法显示出巨大的优势，结构更简单，实施起来也更容易。

1 Introduction 1 引言

Shortest path is one of the most fundamental problems in graph theory, and its algorithms lie at the core of graph algorithm research. In a graph

G = (V, E, w)

with

m = | E |, n = | V |

and non-negative edge weight

w : E \to R_{\geq 0}

, single-source shortest path (SSSP) problem asks for the distances from a given source

s \in V

to all other vertices. Dijkstra’s algorithm [8] computes the distances

dist (s, u)

by dynamic programming. For each vertex

u

, it maintains a temporal distance

d (u)

, which represents the shortest path from

s

u

only passing through the vertices in current

S

, where

S

is the set of visited vertices during algorithm process. In each round of iteration it selects vertex

u

with the smallest

d (u)

from the unvisited nodes. Finally when

S = V, d (u) = dist (s, u)

for all vertex

u

. Advanced data structures with amortized

O (1)

time for insertion and decreasekey, and

O (\log n)

for extract-min, called Fibonacci heap [14] and relaxed heap [10], make the time bound for Dijkstra’s algorithm to

O (m + n \log n)

. This time bound is in the comparisonaddition model where only comparison and addition operations on edge weights are allowed and considered as unit-time operations, which is the most common model for real number inputs. For undirected graphs, Pettie and Ramachandran [25] proposed an SSSP algorithm with running time

O (m α (m, n) + min {n \log n, n \log \log r})

in the comparison-addition model, where

α

is the inverseAckermann function and

r

bounds the ratio of any two edge weights. However, no SSSP algorithm faster than

O (m + n \log n)

has been found for real-weighted graphs without ratio constraints, both for undirected and directed graphs.
最短路径是图论中最基本的问题之一，其算法是图算法研究的核心。在一个图

G = (V, E, w)

中，具有

m = | E |, n = | V |

和非负边权

w : E \to R_{\geq 0}

，单源最短路径（SSSP）问题要求计算从给定源

s \in V

到所有其他顶点的距离。Dijkstra 算法 [8] 通过动态规划计算距离

dist (s, u)

。对于每个顶点

u

，它维护一个临时距离

d (u)

，表示从

s

到

u

的最短路径，仅经过当前

S

中的顶点，其中

S

是算法过程中访问过的顶点集合。在每轮迭代中，它从未访问的节点中选择距离最小的顶点

u

。最后，当

S = V, d (u) = dist (s, u)

对所有顶点

u

完成时。具有摊销

O (1)

时间的高级数据结构用于插入和 decreasekey，以及用于 extract-min 的

O (\log n)

，称为 Fibonacci 堆 [14] 和松弛堆 [10]，使 Dijkstra 算法的时间界限为

O (m + n \log n)

。此时间界限是在比较加法模型中，其中仅允许对边权进行比较和加法操作，并将其视为单位时间操作，这是实数输入中最常见的模型。对于无向图，Pettie 和 Ramachandran [25] 提出了一个在比较加法模型中运行时间为

O (m α (m, n) + min {n \log n, n \log \log r})

的单源最短路径（SSSP）算法，其中

α

是反阿克曼函数，

r

限制了任何两个边权的比率。然而，对于没有比率约束的实权重图，无论是无向图还是有向图，尚未找到比

O (m + n \log n)

更快的 SSSP 算法。

A byproduct of Dijkstra’s algorithm is the sorting of all vertices by their distances from

s

, but the lower bound of

Ω (n \log n)

lies for comparison-based sorting algorithms. Researchers used to believe that this sorting bottleneck existed for many graph problems, and breaking this bottleneck is an important and interesting direction. Yao [7] gave a minimum spanning tree (MST) algorithm with running time

O (m \log \log n)

, citing an unpublished result of

O (m \sqrt{\log n})

by Tarjan. The current best results for MST are the randomized linear time algorithm [22], the deterministic

O (m α (m, n))

-time algorithm [4], and a deterministic algorithm with proven optimal (but unknown) complexity [24]. In the bottleneck path problem, we want to find the path maximizing the minimum edge weight on it between two vertices. Gabow and Tarjan [18] gave an

O (m \log^{*} n)

-time algorithm for s-t bottleneck path problem in directed graphs, which was later improved to randomized

O (m β (m, n))

time [5]. For single-source all-destination bottleneck path problem in directed graphs, there is a recent result of

O (m \sqrt{\log n})

-time randomized algorithm by Duan et al. [11]. For single-source nondecreasing path problem, Virginia V.Williams [34] proposed an algorithm with time bound

O (m \log \log n)

. All the results above are comparison-based though, the techniques in these works, such as local construction or divide-and-conquer approach, hardly works for the shortest path problem. Therefore it remains how to break the sorting bottleneck for SSSP.
Dijkstra 算法的一个副产品是按与

s

的距离对所有顶点进行排序，但

Ω (n \log n)

的下界适用于基于比较的排序算法。研究人员曾认为，这种排序瓶颈在许多图问题中存在，突破这一瓶颈是一个重要且有趣的方向。Yao [7] 提出了一个运行时间为

O (m \log \log n)

的最小生成树 (MST) 算法，引用了 Tarjan 的一项未发表结果

O (m \sqrt{\log n})

。目前 MST 的最佳结果是随机线性时间算法 [22]、确定性

O (m α (m, n))

-时间算法 [4] 和一个具有已证明最优（但未知）复杂度的确定性算法 [24]。在瓶颈路径问题中，我们希望找到在两个顶点之间最大化最小边权重的路径。Gabow 和 Tarjan [18] 提出了一个针对有向图中 s-t 瓶颈路径问题的

O (m \log^{*} n)

-时间算法，后来改进为随机

O (m β (m, n))

时间 [5]。对于有向图中的单源全目标瓶颈路径问题，Duan 等人 [11] 最近提出了一个

O (m \sqrt{\log n})

-时间的随机算法。对于单源非递减路径问题，Virginia V.Williams [34] 提出了一个时间界限为

O (m \log \log n)

的算法。尽管上述所有结果都是基于比较的，但这些工作的技术，如局部构造或分治方法，几乎无法用于最短路径问题。因此，如何打破单源最短路径的排序瓶颈仍然是一个问题。

1.1 Our Results 1.1 我们的结果

In this paper we propose the first SSSP algorithm for undirected real-weighted graphs that breaks the sorting bottleneck.
在本文中，我们提出了第一个针对无向实重图的单源最短路径算法，打破了排序瓶颈。

Theorem 1. In an undirected graph

G = (V, E, w)

with nonnegative edge weights

w : E \to R_{\geq 0}

, there is a comparison-addition based Las-Vegas randomized algorithm that solves the single-source shortest path problem in

O (m \sqrt{\log n \cdot \log \log n})

time, in which the results are always correct and it can achieve this time bound with high probability. The time complexity can be improved to

O (\sqrt{m n \log n} + n \sqrt{\log n \log \log n})

when

m = ω (n)

and

m = o (n \log n)

.
定理 1. 在一个边权非负的无向图

G = (V, E, w)

中，有一种基于比较-加法的拉斯维加斯随机算法，可以在

O (m \sqrt{\log n \cdot \log \log n})

时间内解决单源最短路径问题，结果总是正确，并且可以以高概率达到这个时间界限。当

m = ω (n)

和

m = o (n \log n)

时，时间复杂度可以提高到

O (\sqrt{m n \log n} + n \sqrt{\log n \log \log n})

。

Note that there is a (worst-case) lower bound of

Ω (m + min {n \log n, n \log \log r})

in [25] for
请注意，在[25]中存在一个（最坏情况）下界为

Ω (m + min {n \log n, n \log \log r})

“hierarchy-based” algorithms for undirected real-weighted SSSP, but our algorithm is randomized and not hierarchy-based. See Remark 2 for discussions.
“基于层次”的无向实重 SSSP 算法，但我们的算法是随机的，并不是基于层次的。有关讨论，请参见备注 2。

Technical Overview. The bottleneck of Dijkstra-based algorithm is the priority queue. For this reason, we only add a fraction of vertices into the priority queue. As in many works on distance oracles or spanners, we sample a subset of vertices

R

, and the heap is only for vertices in

R

, then we “bundle” every other vertex

v

to its nearest vertex in

R

, which is called

b (v)

. Then define Ball

(v)

to be the set of vertices closer than

b (v)

v

. Since the algorithm doesn’t know the correct order of most vertices on a shortest path, relaxing only neighbours as in Dijkstra’s algorithm doesn’t work. So when popping a vertex

u \in R

from the heap, we also deal with vertices

v

which are bundled to

u

. In an undirected graph, this also implies that

| dist (s, u) - dist (s, v) |

is not large. Here we relax

v

from vertices in

Ball (v)

and their neighbors, then from

v

we relax neighbors of

v

and vertices in their balls. (To make it easier to describe, we first change the graph to a constant-degree graph with

O (m)

vertices.) Details of the algorithm will be discussed in Section 3, as well as the analysis of correctness and running time. The detailed construction of bundles so that the algorithm can achieve the time bound w.h.p. will be introduced in Section 4. The improvement of time complexity by relaxing the constant-degree constraint will be discussed in Section 5 .
技术概述。基于 Dijkstra 算法的瓶颈是优先队列。因此，我们只将一部分顶点添加到优先队列中。与许多关于距离神谕或生成树的研究一样，我们对顶点

R

进行采样，堆仅用于顶点

R

，然后我们将每个其他顶点

v

“捆绑”到其在

R

中最近的顶点，这称为

b (v)

。然后定义球

(v)

为比

b (v)

更接近

v

的顶点集合。由于算法不知道大多数顶点在最短路径上的正确顺序，仅像 Dijkstra 算法那样放松邻居是行不通的。因此，当从堆中弹出顶点

u \in R

时，我们还处理与

u

捆绑的顶点

v

。在无向图中，这也意味着

| dist (s, u) - dist (s, v) |

不是很大。在这里，我们从顶点

Ball (v)

及其邻居中放松

v

，然后从

v

中放松

v

的邻居和它们的球中的顶点。（为了更容易描述，我们首先将图更改为具有

O (m)

个顶点的常数度图。）算法的细节将在第 3 节中讨论，以及正确性和运行时间的分析。将在第 4 节中介绍捆绑的详细构造，以便算法能够以高概率实现时间界限。第 5 节将讨论通过放宽常数度约束来改善时间复杂度。

Existence of algorithms better than

O (m + n \log n)

for real-weighted SSSP has been open for long. Pettie and Ramachandran’s algorithm [25] works better than

O (n \log n)

if the ratio between maximum and minimum edge weights is not very large. For the integer-weighted case, random access machine (RAM) model is usually adopted, where multiplications, shifts and Boolean operations on edge weights are allowed. There are many works on improving heaps and SSSP algorithms on RAM model with integer weights

[16, 17, 19, 26, 27, 29, 30]

. Finally Thorup gave a linear-time algorithm for undirected graphs [28] and

O (m + n \log \log min {n, C})

for directed graphs [31] where

C

is the maximum edge weight. Recently, almost linear time

O (m^{1 + o (1)} \log C)

algorithms for SSSP with negative weights are also discovered

[2, 6]

.
关于比

O (m + n \log n)

更好的实权重单源最短路径（SSSP）算法的存在问题已经悬而未决很久。Pettie 和 Ramachandran 的算法[25]在最大和最小边权重之间的比率不是很大的情况下表现优于

O (n \log n)

。对于整数权重的情况，通常采用随机访问机器（RAM）模型，在该模型中允许对边权重进行乘法、移位和布尔操作。关于改进 RAM 模型中整数权重的堆和 SSSP 算法的研究有很多

[16, 17, 19, 26, 27, 29, 30]

。最后，Thorup 为无向图提供了一个线性时间算法[28]，并且为有向图提供了

O (m + n \log \log min {n, C})

[31]，其中

C

是最大边权重。最近，几乎线性时间的

O (m^{1 + o (1)} \log C)

负权重 SSSP 算法也被发现

[2, 6]

。

All-pair shortest path (APSP) problem requires the shortest path between every pair of vertices

u, v

in the graph

G

. We can run Dijkstra’s algorithm [8] from all vertices which will have running time

O (m n + n^{2} \log n)

, or use Floyd-Warshall algorithm [12, 32] with running time

O (n^{3})

. Researchers have made many improvements since then [3, 9, 15, 20, 35], but there is still no truly subcubic time

(O (n^{3 - ϵ})

for some constant

ϵ > 0)

APSP algorithm for real-weighted graphs or even graphs with integer weights in

[0, n]

. Williams [33] gave an APSP algorithm with running time

n^{3} / 2^{Θ (\sqrt{\log n})}

for real-weighted graphs. For undirected real-weighted graphs, Pettie and Ramachandran’s APSP algorithm [25] runs in

O (m n \log α (m, n))

time, and for directed real-weighted graphs, Pettie [23] gave an APSP algorithm in

O (m n + n^{2} \log \log n)

time.
全对最短路径（APSP）问题要求图

G

中每对顶点

u, v

之间的最短路径。我们可以从所有顶点运行 Dijkstra 算法 [8]，其运行时间为

O (m n + n^{2} \log n)

，或者使用 Floyd-Warshall 算法 [12, 32]，其运行时间为

O (n^{3})

。自那时以来，研究人员做出了许多改进 [3, 9, 15, 20, 35]，但对于某些常数

ϵ > 0)

的真实权重图或甚至整数权重图，仍然没有真正的亚立方时间

(O (n^{3 - ϵ})

APSP 算法。Williams [33] 提出了一个运行时间为

n^{3} / 2^{Θ (\sqrt{\log n})}

的真实权重图的 APSP 算法。对于无向真实权重图，Pettie 和 Ramachandran 的 APSP 算法 [25] 的运行时间为

O (m n \log α (m, n))

，而对于有向真实权重图，Pettie [23] 提出了一个运行时间为

O (m n + n^{2} \log \log n)

的 APSP 算法。

2 Preliminaries 2 前言

In this paper we work on an undirected graph

G = (V, E, w)

with vertex set

V

, edge set

E \subseteq V^{2}

and non-negative weight function

w : E \to R_{\geq 0}

, also denoted by

w_{u v}

. In an undirected graph

w_{u v} = w_{v u}

holds for all edges

(u, v) \in E

. We denote

n = | V |, m = | E |

as the number of vertices and edges in the graph, and

N (u) = {v : (u, v) \in E}

as the set of neighbors of

u

. For two vertices

u, v \in V, {dist}_{G} (u, v)

is length of the shortest path connecting

u

and

v

, namely the distance of

u

and

v

in graph

G

. The subscript

G

is omitted when the context is clear. Let

s

be the source vertex.
在本文中，我们研究一个无向图

G = (V, E, w)

，其顶点集为

V

，边集为

E \subseteq V^{2}

，并且具有非负权重函数

w : E \to R_{\geq 0}

，也表示为

w_{u v}

。在无向图

w_{u v} = w_{v u}

中，所有边

(u, v) \in E

都成立。我们用

n = | V |, m = | E |

表示图中的顶点和边的数量，用

N (u) = {v : (u, v) \in E}

表示

u

的邻居集合。对于两个顶点

u, v \in V, {dist}_{G} (u, v)

，连接

u

和

v

的最短路径的长度为

u

和

v

在图

G

中的距离。上下标

G

在上下文清晰时省略。设

s

为源顶点。

The target of our algorithm is to find

dist (s, v)

for every

v \in V

. Without loss of generality we assume that

G

is connected, so

m \geq n - 1

.
我们算法的目标是为每个

v \in V

找到

dist (s, v)

。为了不失一般性，我们假设

G

是连通的，因此

m \geq n - 1

。

Constant-Degree Graph. Throughout the paper we need a graph with constant degree. To accomplish this, given a graph

G

, we construct

G^{'}

by a classical transformation (see [13]):
常数度图。在整篇论文中，我们需要一个具有常数度的图。为此，给定一个图

G

，我们通过经典变换构造

G^{'}

（见[13]）：

Substitute each vertex $v$ with a cycle of $| N (v) |$ vertices $x_{v w} (w \in N (v))$ connected with undirected zero-weight edges, that is, for every neighbor $w$ of $v$ , there is a vertex $x_{v w}$ on this cycle.
将每个顶点 $v$ 替换为一个由 $| N (v) |$ 个顶点 $x_{v w} (w \in N (v))$ 组成的循环，这些顶点通过无向零权重边连接，也就是说，对于每个邻居 $w$ 的 $v$ ，在这个循环上有一个顶点 $x_{v w}$ 。
For every edge $(u, v)$ in $G$ , add an undirected edge between corresponding vertices $x_{u v}$ and $x_{v u}$ with weight $w_{u v}$ .
对于每条边 $(u, v)$ 在 $G$ 中，在对应的顶点 $x_{u v}$ 和 $x_{v u}$ 之间添加一条权重为 $w_{u v}$ 的无向边。

We can see distance

{dist}_{G^{'}} (x_{u u^{'}}, x_{v v^{'}}) = {dist}_{G} (u, v)

for arbitrary

u^{'} \in N (u)

and

v^{'} \in N (v)

. Each vertex in

G^{'}

has degree at most 3 , while

G^{'}

being a graph with

O (m)

vertices and

O (m)

edges.
我们可以看到任意

u^{'} \in N (u)

和

v^{'} \in N (v)

的距离

{dist}_{G^{'}} (x_{u u^{'}}, x_{v v^{'}}) = {dist}_{G} (u, v)

。

G^{'}

中的每个顶点的度数最多为 3，而

G^{'}

是一个具有

O (m)

个顶点和

O (m)

条边的图。

Comparison-Addition Model. In this paper our algorithm works under comparison-addition model, in which real numbers are subject to only comparison and addition operations. In this model, each addition and comparison takes unit time, and no other computations on edge weights are allowed.
比较-加法模型。在本文中，我们的算法在比较-加法模型下工作，在该模型中，实数仅接受比较和加法操作。在此模型中，每次加法和比较都需要单位时间，并且不允许对边权进行其他计算。

Fibonacci Heap. Under such a model, it is possible to construct a Fibonacci heap

H

that spends amortized

O (1)

time for initialization, insertion, decrease-key operations, and

O (\log | H |)

time for each extract-min operation [14]. When we extract the minimum element from the heap, we also call that element “popped” from the heap.
斐波那契堆。在这样的模型下，可以构造一个斐波那契堆

H

，其初始化、插入、减键操作的摊销时间为

O (1)

，每次提取最小值操作的时间为

O (\log | H |)

[14]。当我们从堆中提取最小元素时，我们也称该元素为“从堆中弹出”。

3 Main Algorithm 3 主算法

In the following sections we assume that

G

is connected, and each vertex in

G

has degree no more than 3. (There are

O (m)

vertices and

O (m)

edges in

G

, but we still use

O (\log n)

which is equivalent to

O (\log m)

where

n

is the number of vertices in the original graph without degree constraints.)
在接下来的部分中，我们假设

G

是连通的，并且

G

中的每个顶点的度数不超过 3。（在

G

中有

O (m)

个顶点和

O (m)

条边，但我们仍然使用

O (\log n)

，它等价于

O (\log m)

，其中

n

是原始图中没有度数限制的顶点数量。）

Our algorithm is based on original Dijkstra’s algorithm [8]. Since the main bottleneck of Dijkstra’s algorithm is the

O (\log n)

time per every vertex extracted from the Fibonacci heap [14], we only insert a subset

R \subseteq V

of vertices into the heap. Each remaining vertex

v \in V ∖ R

is bundled to its closest vertex in

R

. Throughout the algorithm, vertices are updated only when some vertex

u \in R

is popped from the heap. Our algorithm consists of two stages: bundle construction and Bundle Dijkstra, whose details will be introduced in Section 3.1 and 3.2 respectively.
我们的算法基于原始的 Dijkstra 算法[8]。由于 Dijkstra 算法的主要瓶颈是从 Fibonacci 堆[14]中提取每个顶点的

O (\log n)

时间，我们只将一部分

R \subseteq V

顶点插入堆中。每个剩余的顶点

v \in V ∖ R

与其在

R

中最近的顶点捆绑在一起。在整个算法过程中，只有在某个顶点

u \in R

从堆中弹出时，顶点才会被更新。我们的算法由两个阶段组成：捆绑构建和捆绑 Dijkstra，其细节将在第 3.1 节和第 3.2 节中分别介绍。

To demonstrate the main idea of our algorithm, in this section we first give an algorithm that runs in expected

O (m \sqrt{\log n \cdot \log \log n})

time but not “with high probability”. In Section 4 we give an improved version of the bundle construction stage, leading to an algorithm that runs in

O (m \sqrt{\log n \cdot \log \log n})

time with high probability. Both algorithms always give correct answers.
为了演示我们算法的主要思想，在本节中我们首先给出一个期望运行时间为

O (m \sqrt{\log n \cdot \log \log n})

的算法，但并不是“以高概率”。在第 4 节中，我们给出一个改进的束构造阶段，导致一个以高概率在

O (m \sqrt{\log n \cdot \log \log n})

时间内运行的算法。这两个算法总是给出正确的答案。

3.1 Bundle Construction 3.1 捆绑构建

A simple version of bundle construction works as follows

^{1}

(

k

is a parameter to be determined later):
捆绑构造的简单版本如下

^{1}

（

k

是稍后确定的参数）：

Independently sample each vertex $v \in V ∖ {s}$ with probability $\frac{1}{k}$ to form set $R$ , then add $s$ into $R$ .
独立地以概率 $\frac{1}{k}$ 对每个顶点 $v \in V ∖ {s}$ 进行采样以形成集合 $R$ ，然后将 $s$ 添加到 $R$ 中。
For each vertex $v \notin R$ , run Dijkstra’s algorithm started from $v$ until first vertex of $R$ is extracted from the heap, denoted by $b (v)$ . Therefore $b (v)$ is one of the closest vertices in $R$ to $v$ , i.e., $b (v) \in \arg min_{u \in R} dist (u, v)$ . We say that $v$ is bundled to $b (v)$ .
对于每个顶点 $v \notin R$ ，运行从 $v$ 开始的 Dijkstra 算法，直到从堆中提取出 $R$ 的第一个顶点，记为 $b (v)$ 。因此 $b (v)$ 是 $R$ 中离 $v$ 最近的顶点之一，即 $b (v) \in \arg min_{u \in R} dist (u, v)$ 。我们说 $v$ 被捆绑到 $b (v)$ 。
For each $u \in R$ , let $b (u) = u$ , and $Bundle (u) = {v : u = b (v)}$ be the set of vertices bundled to $u$ . By definition, ${Bundle (u)}_{u \in R}$ forms a partition of the vertex set $V$ .
对于每个 $u \in R$ ，设 $b (u) = u$ 和 $Bundle (u) = {v : u = b (v)}$ 为捆绑到 $u$ 的顶点集合。根据定义， ${Bundle (u)}_{u \in R}$ 形成顶点集合 $V$ 的一个划分。
For each vertex $v \notin R$ , define $Ball (v) = {w \in V : dist (v, w) < dist (v, b (v))}$ , that is, the set of vertices closer to $v$ than its bundled vertex $b (v)$ . In the previous Dijkstra’s algorithm we can get $Ball (v)$ and also values of $dist (v, w)$ for all $w \in Ball (v) \cup {b (v)}$ .
对于每个顶点 $v \notin R$ ，定义 $Ball (v) = {w \in V : dist (v, w) < dist (v, b (v))}$ ，即比其捆绑顶点 $b (v)$ 更接近 $v$ 的顶点集合。在之前的 Dijkstra 算法中，我们可以得到 $Ball (v)$ ，并且还可以得到所有 $w \in Ball (v) \cup {b (v)}$ 的 $dist (v, w)$ 值。

Time Analysis of Bundle Construction. For each vertex

v \notin R

, without loss of generality we assume its Dijkstra’s algorithm breaks tie in a deterministic way. Therefore, the order of vertices extracted from heap is fixed.
束构建的时间分析。对于每个顶点

v \notin R

，不失一般性，我们假设其 Dijkstra 算法以确定性方式打破平局。因此，从堆中提取的顶点顺序是固定的。

We can see

E [| R |] = O (m / k)

. For each vertex

v \notin R

, let

S_{v}

be the set of vertices extracted before its Dijkstra’s algorithm stops, then

Ball (v) ⊊ S_{v}

. By definition of

R, | S_{v} |

follows geometric distribution with success probability

\frac{1}{k}

, thus

E [| S_{v} |] = k

and

E [| Ball (v) |] \leq k

. By constant degree property, the number of vertices ever added into the heap is also

O (| S_{v} |)

, so the total time of the bundle construction is

O (\sum_{v \in V ∖ R} E [| S_{v} | \log | S_{v} |]) = O (m k \log k)

in expectation.
我们可以看到

E [| R |] = O (m / k)

。对于每个顶点

v \notin R

，设

S_{v}

为在其 Dijkstra 算法停止之前提取的顶点集合，则

Ball (v) ⊊ S_{v}

。根据

R, | S_{v} |

的定义，遵循成功概率为

\frac{1}{k}

的几何分布，因此

E [| S_{v} |] = k

和

E [| Ball (v) |] \leq k

。根据常数度性质，加入堆中的顶点数量也是

O (| S_{v} |)

，因此捆绑构造的总时间在期望上是

O (\sum_{v \in V ∖ R} E [| S_{v} | \log | S_{v} |]) = O (m k \log k)

。
Remark 1. One may argue that

x \log x

is a convex function so that

E [| S_{v} | \log | S_{v} |] = O (k \log k)

does not trivially hold due to Jensen’s inequality. Thanks to an anonymous reviewer, just notice that

E [{| S_{v} |}^{2}] = 2 k^{2} - k = O (k^{2})

and

\sqrt{x} \log x

is a concave function when

x \geq 1

.
备注 1. 有人可能会争辩说

x \log x

是一个凸函数，因此

E [| S_{v} | \log | S_{v} |] = O (k \log k)

并不因为詹森不等式而显然成立。感谢一位匿名审稿人，只需注意当

x \geq 1

时

E [{| S_{v} |}^{2}] = 2 k^{2} - k = O (k^{2})

和

\sqrt{x} \log x

是一个凹函数。

3.2 Bundle Dijkstra 3.2 捆绑 Dijkstra

Given the set

R

and the partition of bundles, the main algorithm works as follows, with pseudocode given in Algorithm 1:
给定集合

R

和捆绑的划分，主要算法如下工作，伪代码见算法 1：

Initially we set

d (s) = 0

and

d (v) = + \infty

for all other vertex

v

, and insert all vertices of

R

into a Fibonacci heap [14]. Whenever we pop a vertex

u \in R

from the heap, we update the distances by the following steps. (Here relaxing a vertex

v

by a value

D

means that we update

d (v)

min {d (v), D}

.)
最初，我们为所有其他顶点

v

设置

d (s) = 0

和

d (v) = + \infty

，并将

R

的所有顶点插入一个斐波那契堆 [14]。每当我们从堆中弹出一个顶点

u \in R

时，我们通过以下步骤更新距离。（这里通过值

D

放松顶点

v

意味着我们将

d (v)

更新为

min {d (v), D}

。）

For every vertex $v$ bundled to $u$ , we need to find the exact value of $dist (s, v)$ . First relax $v$ by $d (u) + dist (u, v)$ ; then for every vertex $y \in Ball (v)$ , relax $v$ by $d (y) + dist (y, v)$ ; and for every $z_{2} \in Ball (v) \cup {v}$ and $z_{1} \in N (z_{2})$ , relax $v$ by $d (z_{1}) + w_{z_{1}, z_{2}} + dist (z_{2}, v)$ . That is, we update $d (v)$ by its bundled vertex $u$ , vertices in $Ball (v)$ , and vertices neighboring to $v$ and $Ball (v)$ .
对于每个与 $u$ 绑定的顶点 $v$ ，我们需要找到 $dist (s, v)$ 的确切值。首先通过 $d (u) + dist (u, v)$ 放松 $v$ ; 然后对于每个顶点 $y \in Ball (v)$ ，通过 $d (y) + dist (y, v)$ 放松 $v$ ; 对于每个 $z_{2} \in Ball (v) \cup {v}$ 和 $z_{1} \in N (z_{2})$ ，通过 $d (z_{1}) + w_{z_{1}, z_{2}} + dist (z_{2}, v)$ 放松 $v$ 。也就是说，我们通过其绑定的顶点 $u$ 、在 $Ball (v)$ 中的顶点，以及与 $v$ 和 $Ball (v)$ 邻接的顶点来更新 $d (v)$ 。
After updating $d (x)$ for every $x \in Bundle (u)$ , we update the vertices $y \in N (x)$ and vertices $z_{1} \in Ball (y)$ . That is, relaxing $y$ by $d (x) + w_{x, y}$ for all $y \in N (x)$ and then relaxing $z_{1}$ by $d (x) + w_{x, y} + dist (y, z_{1})$ for all $z_{1} \in Ball (y)$ .
在每个 $x \in Bundle (u)$ 更新 $d (x)$ 后，我们更新顶点 $y \in N (x)$ 和顶点 $z_{1} \in Ball (y)$ 。也就是说，对所有 $y \in N (x)$ 通过 $d (x) + w_{x, y}$ 放松 $y$ ，然后对所有 $z_{1} \in Ball (y)$ 通过 $d (x) + w_{x, y} + dist (y, z_{1})$ 放松 $z_{1}$ 。
Whenever we update a vertex $v \notin R$ , we also relax its bundled vertex $b (v)$ by $d (v) +$ $dist (v, b (v)$ ). (But later we will see this is only needed in Step 2 but not Step 1, since in Step $1 v$ is bundled to $u$ , but the distance $dist (s, u)$ is already found when popping $u$ from the heap.)
每当我们更新一个顶点 $v \notin R$ 时，我们也会通过 $d (v) +$ $dist (v, b (v)$ 来松弛其捆绑顶点 $b (v)$ 。（但稍后我们会看到这仅在第 2 步中需要，而在第 1 步中不需要，因为在第 $1 v$ 步中捆绑到 $u$ ，但当从堆中弹出 $u$ 时，距离 $dist (s, u)$ 已经找到。）
The following observation holds naturally from the algorithm.
以下观察自然地从算法中得出。
Observation 2. $d (v) \geq dist (s, v)$ always holds for all $v \in V$ .
观察 2。 $d (v) \geq dist (s, v)$ 对所有 $v \in V$ 始终成立。

Algorithm 1: BundleDijkstra \((G, s)\)
    Input : A graph \(G=(V, E, w)\) and starting vertex \(s \in V\)
    Output: Distance \(d(v)\) from \(s\) to \(v\) for every vertex \(v \in V\)
    Construct Bundles as described in Section 3.1;
    Set label \(d(s) \leftarrow 0\) and \(d(v) \leftarrow+\infty\) for all \(v \in V \backslash\{s\}\);
    Initialize Fibonacci heap \(H\) with all vertices of \(R\) and key \(d(\cdot)\);
    while \(H\) is not empty do
        \(u \leftarrow H\).ExtractMin();
        foreach \(v \in \operatorname{Bundle}(u)\) do // Step 1
            \(\operatorname{Relax}(v, d(u)+\operatorname{dist}(u, v))\);
            foreach \(y \in \operatorname{Ball}(v)\) do
            \(\operatorname{Relax}(v, d(y)+\operatorname{dist}(y, v)) ;\)
            foreach \(z_{2} \in \operatorname{Ball}(v) \cup\{v\}\) do
                    foreach \(z_{1} \in N\left(z_{2}\right)\) do
                    \(\operatorname{ReLax}\left(v, d\left(z_{1}\right)+w_{z_{1}, z_{2}}+\operatorname{dist}\left(z_{2}, v\right)\right) ;\)
            foreach \(x \in \operatorname{Bundle}(u)\) do // Step 2
            foreach \(y \in N(x)\) do
                    \(\operatorname{Relax}\left(y, d(x)+w_{x, y}\right)\);
                    foreach \(z_{1} \in \operatorname{Ball}(y)\) do
                    \(\operatorname{Relax}\left(z_{1}, d(x)+w_{x, y}+\operatorname{dist}\left(y, z_{1}\right)\right) ;\)
    function \(\operatorname{Relax}(v, D)\) :
            if \(D<d(v)\) then
            \(d(v) \leftarrow D ;\)
            if \(v \in H\) then
                            \(H\).DecreaseKey \((v, D)\)
            else if \(v \notin R\) then
                    \(\operatorname{ReLax}(\mathrm{b}(v), d(v)+\operatorname{dist}(v, \mathrm{~b}(v))) \quad / /\) Step 3

Time Analysis for Bundle Dijkstra. For the Bundle Dijkstra stage, only vertices in

R

are inserted into heap, thus the extract-min operation only takes

O (| R | \log n)

time in total. Since every vertex in

V ∖ R

only appears once as

v

and

x

in Step 1 and Step 2 , respectively, and by constant degree property, every vertex appears constant times as the vertex

y \in N (x)

in Step 2. We can see the number of vertices

z_{1}, z_{2}

in Step 1 for every

v

O (| Ball (v) |)

, and the number of vertices

z_{1}

in Step 2 for every

y

O (| Ball (y) |)

. Also note that the recursive call of Relax in Step 3 can only recurse once since

b (v) \in R

. So the total time for Step 1, 2 and 3 is

O (\sum_{v \in V ∖ R} | Ball (v) |)

. Thus, the time of the bundle Dijkstra stage is

E [O (| R | \cdot \log n + \sum_{v \in V ∖ R} | Ball (v) |)] = O (\frac{m}{k} \log n + m k)

in expectation.
束迪杰斯特拉的时间分析。在束迪杰斯特拉阶段，只有

R

中的顶点被插入到堆中，因此提取最小值操作总共只需

O (| R | \log n)

时间。由于

V ∖ R

中的每个顶点在步骤 1 和步骤 2 中分别只出现一次作为

v

和

x

，并且根据常数度性质，每个顶点在步骤 2 中作为顶点

y \in N (x)

出现的次数是常数。我们可以看到步骤 1 中每个

v

的顶点数量是

O (| Ball (v) |)

，而步骤 2 中每个

y

的顶点数量是

O (| Ball (y) |)

。还要注意，步骤 3 中 Relax 的递归调用只能递归一次，因为

b (v) \in R

。因此步骤 1、2 和 3 的总时间是

O (\sum_{v \in V ∖ R} | Ball (v) |)

。因此，束迪杰斯特拉阶段的期望时间是

E [O (| R | \cdot \log n + \sum_{v \in V ∖ R} | Ball (v) |)] = O (\frac{m}{k} \log n + m k)

。

Now, we can see that the expected total time of the two stages is

O (\frac{m}{k} \log n + m k \log k)

, which is minimized to

O (m \sqrt{\log n \cdot \log \log n})

if we choose

k = \sqrt{\frac{\log n}{\log \log n}}

. We move to explain our main ideas of the correctness proof. A formal proof is given in Section 3.3.
现在，我们可以看到两个阶段的预期总时间是

O (\frac{m}{k} \log n + m k \log k)

，如果我们选择

k = \sqrt{\frac{\log n}{\log \log n}}

，则最小化为

O (m \sqrt{\log n \cdot \log \log n})

。我们接下来将解释我们正确性证明的主要思路。正式证明在第 3.3 节中给出。

Main ideas. The following propositions hold in the algorithm. (Here the iteration of

u

means the iteration performed when popping

u \in R

; a real distance

dist (s, v)

is found means

d (v) = dist (s, v)

already holds.)
主要思想。以下命题在算法中成立。（这里

u

的迭代意味着在弹出

u \in R

时执行的迭代；找到一个真实距离

dist (s, v)

意味着

d (v) = dist (s, v)

已经成立。）

Proposition 3. When popping

u \in R

from the heap, its distance

dist (s, u)

is already found.
命题 3。当从堆中弹出

u \in R

时，其距离

dist (s, u)

已经找到。
Proposition 4. After Step 1 in the iteration of

u

dist (s, v)

for all

v \in Bundle (u)

are found.
命题 4。在迭代

u

的第 1 步之后，找到所有

dist (s, v)

和

v \in Bundle (u)

。
The following lemmas contain the main ideas of the algorithm.
以下引理包含算法的主要思想。
Lemma 5. For any vertex

u \in R

and any path

P

from

s

u

, if

P

goes through vertex

y

dist (s, b (y))

is at most the length of

P

.
引理 5. 对于任何顶点

u \in R

和从

s

到

u

的任何路径

P

，如果

P

经过顶点

y

，则

dist (s, b (y))

至多是

P

的长度。

Proof. dist

(s, y)

is at most the length of subpath of

P

from

s

y

. By definition of

b (y), dist (y, b (y))

is at most the length of subpath of

P

from

y

u

. Concatenating two subpaths together,

dist (s, b (y)) \leq

dist (s, y) + dist (y, b (y))

is at most the length of

P

.
证明。dist

(s, y)

至多是

s

到

y

的

P

的子路径的长度。根据

b (y), dist (y, b (y))

的定义，至多是

y

到

u

的

P

的子路径的长度。将两个子路径连接在一起，

dist (s, b (y)) \leq

dist (s, y) + dist (y, b (y))

至多是

P

的长度。

Lemma 5 shows that for any vertex

u \in R

, the shortest path from

s

u

only contains vertices

y

with

dist (s, b (y)) \leq dist (s, u)

. This is the intuition why vertices of

R

are popped in increasing order of

dist (s, \cdot)

. However, the shortest path from

s

to some vertex

v \in Bundle (u)

may go through some vertex

y

with

dist (s, b (y)) \geq dist (s, u)

, that is,

b (y)

is still not popped from the heap. But surprisingly, with the ideas of Lemma 6 we can deal with this case even before the iteration of

b (y)

.
引理 5 显示，对于任何顶点

u \in R

，从

s

到

u

的最短路径仅包含顶点

y

和

dist (s, b (y)) \leq dist (s, u)

。这就是为什么

R

的顶点按

dist (s, \cdot)

的递增顺序弹出的直觉。然而，从

s

到某个顶点

v \in Bundle (u)

的最短路径可能会经过某个顶点

y

和

dist (s, b (y)) \geq dist (s, u)

，也就是说，

b (y)

仍然没有从堆中弹出。但令人惊讶的是，借助引理 6 的思想，我们甚至可以在

b (y)

的迭代之前处理这种情况。

Lemma 6. For a vertex

v \notin R

, if the shortest path from

s

v

is shorter than

dist (s, b (v)) +

dist (b (v), v)

, and it goes through a vertex

y

(other than

v

) such that

dist (s, b (y)) \geq dist (s, b (v))

, then on the shortest path from

y

v

there are two adjacent vertices

z_{1}, z_{2}

such that

z_{1} \in Ball (y) \cup {y}

and

z_{2} \in Ball (v) \cup {v}

.
引理 6. 对于一个顶点

v \notin R

，如果从

s

到

v

的最短路径比

dist (s, b (v)) +

dist (b (v), v)

短，并且它经过一个顶点

y

（不同于

v

）使得

dist (s, b (y)) \geq dist (s, b (v))

，那么在从

y

到

v

的最短路径上，有两个相邻的顶点

z_{1}, z_{2}

使得

z_{1} \in Ball (y) \cup {y}

和

z_{2} \in Ball (v) \cup {v}

。

Proof. We have

dist (y, v) = dist (s, v) - dist (s, y)

and

dist (s, v) < dist (s, b (v)) + dist (b (v), v)

. By triangle inequality,

dist (s, y) \geq dist (s, b (y)) - dist (y, b (y))

, and by

dist (s, b (y)) \geq dist (s, b (v))

,
证明。我们有

dist (y, v) = dist (s, v) - dist (s, y)

和

dist (s, v) < dist (s, b (v)) + dist (b (v), v)

。根据三角不等式，

dist (s, y) \geq dist (s, b (y)) - dist (y, b (y))

，并且根据

dist (s, b (y)) \geq dist (s, b (v))

，

dist (y, v) < dist (b (v), v) + dist (y, b (y)) + dist (s, b (v)) - dist (s, b (y)) \leq dist (b (v), v) + dist (y, b (y))

Let

z_{1}

be the last vertex on the shortest path from

y

v

satisfying

dist (y, z_{1}) < dist (y, b (y))

, so

z_{1} \in Ball (y)

. Then

z_{2}

will be the next vertex after

z_{1}

, so

dist (y, z_{2}) \geq dist (y, b (y))

, and

dist (z_{2}, v) <

dist (v, b (v))

, so

z_{2} \in Ball (v)

. (If

dist (y, b (y)) = 0

then

z_{1} = y

, and if

dist (y, v) < dist (y, b (y))

then

z_{2} = v

and

z_{1}

is the vertex before

v

.)
让

z_{1}

成为从

y

到

v

的最短路径上的最后一个顶点，满足

dist (y, z_{1}) < dist (y, b (y))

，所以

z_{1} \in Ball (y)

。然后

z_{2}

将是

z_{1}

之后的下一个顶点，所以

dist (y, z_{2}) \geq dist (y, b (y))

，并且

dist (z_{2}, v) <

dist (v, b (v))

，所以

z_{2} \in Ball (v)

。（如果

dist (y, b (y)) = 0

那么

z_{1} = y

，如果

dist (y, v) < dist (y, b (y))

那么

z_{2} = v

并且

z_{1}

是

v

之前的顶点。）

Then we can see Proposition 3 and 4 hold throughout the algorithm iteratively: (A formal proof will be given in Section 3.3.)
然后我们可以看到命题 3 和 4 在算法的迭代过程中始终成立：（正式证明将在第 3.3 节中给出。）

When we pop the source $s$ from the heap, $d (s) = 0$ , and the distances $dist (s, v)$ for all $v \in Bundle (s)$ are found in the bundle construction step, and can be put in $d (v)$ in Step 1.
当我们从堆中弹出源 $s$ ， $d (s) = 0$ ，并且在捆绑构建步骤中找到所有 $v \in Bundle (s)$ 的距离 $dist (s, v)$ ，可以在第 1 步中放入 $d (v)$ 。
Assume Proposition 4 holds for the first $i$ vertices popped, so the real distances for all vertices bundled to popped vertices are found after Step 1. By Step 2 and 3, we can see for all unpopped $u \in R$ , the distance $dist (s, u)$ can be found if the shortest path from $s$ to $u$ does not go through vertices bundled to other unpopped vertices in the heap. If the next popped vertex $u^{'}$ does not satisfy this, let $y$ be the first vertex on the shortest path from $s$ to $u^{'}$ which is bundled to an unpopped vertex $b (y)$ other than $u^{'}$ , so $dist (s, b (y))$ can be found. By Lemma $5, dist (s, b (y)) \leq dist (s, u^{'})$ , so if $d (u^{'}) > dist (s, u^{'}), b (y)$ will be the next popped vertex. Thus, $dist (s, u^{'})$ for the next popped vertex $u^{'}$ is found before it is popped.
假设命题 4 对前 $i$ 个弹出顶点成立，因此在步骤 1 之后，所有与弹出顶点捆绑的顶点的实际距离都已找到。通过步骤 2 和 3，我们可以看到对于所有未弹出 $u \in R$ ，如果从 $s$ 到 $u$ 的最短路径不经过与堆中其他未弹出顶点捆绑的顶点，则可以找到距离 $dist (s, u)$ 。如果下一个弹出顶点 $u^{'}$ 不满足这一条件，则让 $y$ 为从 $s$ 到 $u^{'}$ 的最短路径上第一个与未弹出顶点 $b (y)$ （而不是 $u^{'}$ ）捆绑的顶点，因此可以找到 $dist (s, b (y))$ 。根据引理 $5, dist (s, b (y)) \leq dist (s, u^{'})$ ，如果 $d (u^{'}) > dist (s, u^{'}), b (y)$ 将是下一个弹出顶点。因此，在下一个弹出顶点 $u^{'}$ 被弹出之前， $dist (s, u^{'})$ 已找到。
If an unpopped vertex $u^{'} \in R$ is updated in the iteration of popped vertex $u$ , the new path to $u^{'}$ must go through a vertex in Bundle $(u)$ . By Lemma 5, $d (u^{'})$ cannot be updated to be smaller than $dist (s, u)$ , so the unpopped vertices must have longer or equal distances than any popped vertex.
如果在弹出顶点 $u$ 的迭代中更新了一个未弹出的顶点 $u^{'} \in R$ ，那么到 $u^{'}$ 的新路径必须经过 Bundle $(u)$ 中的一个顶点。根据引理 5， $d (u^{'})$ 不能被更新为小于 $dist (s, u)$ ，因此未弹出的顶点的距离必须大于或等于任何弹出顶点的距离。
Thus when popping a vertex $u \in R$ , its $distance dist (s, u)$ is already found. For all vertex $v \in Bundle (u)$ , if $dist (s, v)$ is not directly obtained by $d (u) + dist (u, v)$ , that is, $dist (s, v) <$ $dist (s, u) + dist (u, v)$ , let $x$ be the last vertex on the shortest path from $s$ to $v$ such that $b (x)$ is popped before $u$ , and let $y$ be the next vertex after $x$ . We can see $dist (s, b (y)) \geq dist (s, u)$ , so by Lemma 6 , we get such $z_{1}$ and $z_{2}$ . Then from Proposition $4 dist (s, x)$ can be found in Step 1 in the iteration of $b (x)$ , then $dist (s, z_{1})$ can be found in Step 2 of that iteration. In this iteration of $u$ , $dist (s, v)$ can be set to $dist (s, z_{1}) + w_{z_{1}, z_{2}} + dist (z_{2}, v)$ in Step 1, so Proposition 4 still holds after this iteration.
因此，当弹出一个顶点 $u \in R$ 时，它的 $distance dist (s, u)$ 已经被找到。对于所有顶点 $v \in Bundle (u)$ ，如果 $dist (s, v)$ 不是通过 $d (u) + dist (u, v)$ 直接获得的，也就是说， $dist (s, v) <$ $dist (s, u) + dist (u, v)$ ，让 $x$ 成为从 $s$ 到 $v$ 的最短路径上的最后一个顶点，使得 $b (x)$ 在 $u$ 之前被弹出，并让 $y$ 成为在 $x$ 之后的下一个顶点。我们可以看到 $dist (s, b (y)) \geq dist (s, u)$ ，因此根据引理 6 ，我们得到这样的 $z_{1}$ 和 $z_{2}$ 。然后从命题 $4 dist (s, x)$ 可以在 $b (x)$ 的迭代的第 1 步中找到，然后在该迭代的第 2 步中可以找到 $dist (s, z_{1})$ 。在这次 $u$ 的迭代中， $dist (s, v)$ 可以在第 1 步中设置为 $dist (s, z_{1}) + w_{z_{1}, z_{2}} + dist (z_{2}, v)$ ，因此命题 4 在这次迭代后仍然成立。

3.3 Proof of Correctness
3.3 正确性证明

We give a formal proof based on the pseudocode of Algorithm 1. Define

u_{i} \in R

as the vertex extracted in the

i

-th iteration of while-loop in Algorithm 1. Our key lemma in the following shows the main properties of the algorithm, therefore Bundle Dijkstra is correct no matter how

R

is chosen.
我们给出一个基于算法 1 伪代码的正式证明。将

u_{i} \in R

定义为在算法 1 的 while 循环第

i

次迭代中提取的顶点。我们下面的关键引理展示了算法的主要属性，因此无论

R

如何选择，Bundle Dijkstra 都是正确的。

Lemma 7. The following properties hold for any

i \geq 1

in Bundle Dijkstra (Algorithm 1):
引理 7. 以下属性适用于捆绑 Dijkstra (算法 1) 中的任何

i \geq 1

When $u_{i}$ is extracted from the heap, $d (u_{i}) = dist (s, u_{i})$ holds.
当从堆中提取 $u_{i}$ 时， $d (u_{i}) = dist (s, u_{i})$ 保持不变。
After $i$ -th iteration of the while-loop, $d (u) \geq d (u_{i})$ for all $u \in R ∖ {u_{j}}_{j \leq i}$ .
在第 $i$ 次 while 循环迭代后， $d (u) \geq d (u_{i})$ 对所有 $u \in R ∖ {u_{j}}_{j \leq i}$ 。
After Step 1 of $i$ -th iteration of the while-loop, $d (v) = dist (s, v)$ for all $v \in Bundle (u_{i})$ .
在 while 循环的第 $i$ 次迭代的第 1 步之后， $d (v) = dist (s, v)$ 对所有 $v \in Bundle (u_{i})$ 。

Proof. We shall prove the lemma by induction on

i

.
证明。我们将通过对

i

的归纳来证明这个引理。
The lemma holds for

i = 1

since

d (s) = 0

and

d (v) = dist (s, v)

for all

v \in Bundle (s)

after Line 7.
该引理在

i = 1

成立，因为在第 7 行之后，对于所有

v \in Bundle (s)

，

d (s) = 0

和

d (v) = dist (s, v)

。

Suppose the lemma holds for every

i \leq t - 1

, consider the case

i = t

.
假设引理对每个

i \leq t - 1

都成立，考虑情况

i = t

。

Consider a shortest path $P$ from $s$ to $u_{t}$ . Let $x$ be the last vertex on $P$ such that $x \in Bundle (u_{j})$ for some $j < t$ , and $y$ be the next one after $x$ , hence $y \in Bundle (u)$ for some $u \in R ∖ {u_{ℓ}}_{ℓ < t}$ .
考虑从 $s$ 到 $u_{t}$ 的最短路径 $P$ 。设 $x$ 为 $P$ 上最后一个顶点，使得 $x \in Bundle (u_{j})$ 对于某个 $j < t$ ，而 $y$ 为在 $x$ 之后的下一个顶点，因此 $y \in Bundle (u)$ 对于某个 $u \in R ∖ {u_{ℓ}}_{ℓ < t}$ 。

Figure 1: Illustration of the shortest path from

s

u_{t}

.
图 1：从

s

到

u_{t}

的最短路径示意图。

By Property 3 of induction hypothesis

d (x) = dist (s, x)

after Step 1 of

j

-th iteration. After that the algorithm updates

d (y)

in Line 15 since

y \in N (x)

, and further

d (u)

.
根据归纳假设的属性 3，在第

j

次迭代的第 1 步之后。之后，算法在第 15 行更新

d (y)

，因为

y \in N (x)

，并进一步

d (u)

。
Therefore after

(t - 1)

-th iteration

d (y) = dist (s, x) + dist (x, y) = dist (s, y)

and

d (u) \leq

dist (s, y) + dist (y, u)

. Further:
因此在第

(t - 1)

次迭代后

d (y) = dist (s, x) + dist (x, y) = dist (s, y)

和

d (u) \leq

dist (s, y) + dist (y, u)

。进一步：

\begin{aligned} d (u) & \leq dist (s, y) + dist (y, u) \\ \leq dist (s, y) + dist (y, u_{t}) \\ = dist (s, u_{t}) \\ \leq d (u_{t}) . \end{aligned}

= dist (s, u_{t}) (y on shortest path)

On the other hand, the algorithm extracts

u_{t}

from Fibonacci heap

H

immediately after

(t - 1)

-th iteration, thus

d (u_{t}) \leq d (u)

. So all the inequalities above should be equations, thus

d (u_{t}) = dist (s, u_{t})

.
另一方面，算法在第

(t - 1)

次迭代后立即从斐波那契堆

H

中提取

u_{t}

，因此

d (u_{t}) \leq d (u)

。因此，上述所有不等式应为方程，因此

d (u_{t}) = dist (s, u_{t})

。
2. When executing Line 5 of

t

-th iteration,

d (u) \geq d (u_{t})

holds for every

u \in R ∖ {u_{j}}_{j \leq t}

since

H

is a Fibonacci heap. Suppose

d (u) < d (u_{t})

for some

u \in R ∖ {u_{j}}_{j \leq t}

after

t

-th iteration. The further updates on

d (u)

must start from

d (x)

for some

x \in Bundle (u_{t})

. For last such update, applying Lemma 5 on this path from

s

x

then to

u

, we have:
2. 当执行第

t

次迭代的第 5 行时，由于

H

是一个斐波那契堆，

d (u) \geq d (u_{t})

对每个

u \in R ∖ {u_{j}}_{j \leq t}

都成立。假设在第

t

次迭代后，对于某个

u \in R ∖ {u_{j}}_{j \leq t}

有

d (u) < d (u_{t})

。对

d (u)

的进一步更新必须从某个

x \in Bundle (u_{t})

的

d (x)

开始。对于最后一次这样的更新，应用引理 5 在从

s

到

x

再到

u

的路径上，我们有：

\begin{aligned} d (u) & \geq dist (s, u_{t}) \\ = d (u_{t}), \end{aligned}

leading to contradiction.
导致矛盾。
3. We want to show that

d (v) = dist (s, v)

holds for all

v \in Bundle (u_{t})

. Suppose there exists a vertex

v \in Bundle (u_{t})

such that

d (v) > dist (s, v)

after Step 1. Denote

P

as the shortest path from

s

v

. Let

x

be the last vertex on

P

such that

x \in Bundle (u_{j})

for some

j < t

, and

y

be the next one after

x

P

, hence

y \in Bundle (u)

for some

u \in R ∖ {u_{ℓ}}_{ℓ < t}

. By Property 3 of induction hypothesis,

d (x) = dist (s, x)

after Step 1 of

j

-th iteration. Same as above we can show that

d (y) = dist (s, x) + dist (x, y) = dist (s, y)

and

d (u) \leq dist (s, y) + dist (y, u)

(where

u = b (y))

before

t

-th iteration. We have:
3. 我们想要证明

d (v) = dist (s, v)

对所有

v \in Bundle (u_{t})

成立。假设存在一个顶点

v \in Bundle (u_{t})

，使得在第 1 步之后

d (v) > dist (s, v)

。将

P

表示为从

s

到

v

的最短路径。设

x

为

P

上的最后一个顶点，使得对于某个

j < t

，有

x \in Bundle (u_{j})

，而

y

为在

P

上的

x

之后的下一个顶点，因此对于某个

u \in R ∖ {u_{ℓ}}_{ℓ < t}

，有

y \in Bundle (u)

。根据归纳假设的性质 3，

d (x) = dist (s, x)

在第

j

次迭代的第 1 步之后。与上述相同，我们可以证明

d (y) = dist (s, x) + dist (x, y) = dist (s, y)

和

d (u) \leq dist (s, y) + dist (y, u)

（其中

u = b (y))

在第

t

次迭代之前。我们有：

\begin{aligned} dist (s, y) & \geq d (u) - dist (y, u) . \\ dist (s, v) & < d (v) \\ \leq d (u_{t}) + dist (u_{t}, v) . \end{aligned} (Assumption)) (d(v) updated in Line 7)

On the other hand,

d (u) \geq d (u_{t})

after

t

-th iteration by Property 2 . Since

d (u_{t})

doesn’t change (Property 1 and Observation 2), and

d (u)

can only decrease in

t

-th iteration, so

d (u) \geq d (u_{t})

holds throughout

t

-th iteration. Hence:
另一方面，

d (u) \geq d (u_{t})

在

t

-次迭代后根据性质 2。由于

d (u_{t})

没有变化（性质 1 和观察 2），并且

d (u)

只能在

t

-次迭代中减少，因此

d (u) \geq d (u_{t})

在整个

t

-次迭代中成立。因此：

dist (y, v) = dist (s, v) - dist (s, y) < dist (u_{t}, v) + dist (y, u),

Figure 2: Left: Illustration of the shortest path from

s

v

d (v) > dist (s, v)

. Right: A closer look at path

x

v

dist (y, v) \geq dist (u_{t}, v)

.
图 2：左：如果

d (v) > dist (s, v)

，从

s

到

v

的最短路径示意图。右：如果

dist (y, v) \geq dist (u_{t}, v)

，对路径

x

到

v

的更近一步观察。
while the equation holds since

y

lies on the shortest path from

s

v

.
当方程成立时，因为

y

位于从

s

到

v

的最短路径上。
Therefore there are two possible cases:
因此有两种可能的情况：

$dist (y, v) < dist (u_{t}, v)$ .

In this case

y \in Ball (v)

, so we can update

d (v)

dist (s, y) + dist (y, v)

on Line 9 , contradicting to

d (v) > dist (s, v)

.
在这种情况下

y \in Ball (v)

，所以我们可以在第 9 行将

d (v)

更新为

dist (s, y) + dist (y, v)

，与

d (v) > dist (s, v)

矛盾。

$dist (y, v) \geq dist (u_{t}, v)$ .

First, by Inequality (1),

dist (y, u) > dist (y, v) - dist (u_{t}, v) \geq 0

. Let

z_{1}

be the last vertex on path

P

with

dist (y, z_{1}) < dist (y, u)

, we have

z_{1} \in Ball (y)

. Let

z_{2}

be the next vertex on the path, then

dist (y, z_{2}) \geq dist (y, u)

so dist (z_{2}, v) = dist (y, v) - dist (y, z_{2}) \leq

dist (y, v) - dist (y, u) < dist (u_{t}, v)

, that is,

z_{2} \in Ball (v)

. (If

z_{2}

does not exist, then

z_{1} = v

.) By Property 3 of induction hypothesis,

d (x) = dist (s, x)

just after Step 1 of

j

-th iteration, so

d (z_{1})

is updated to

dist (s, z_{1})

in Line 17 of

j

-th iteration. Therefore

d (v)

is updated to

dist (s, v)

in Line 12 of

t

-th iteration (since

j < t

), contradicting the assumption.
首先，根据不等式 (1)，

dist (y, u) > dist (y, v) - dist (u_{t}, v) \geq 0

。设

z_{1}

为路径

P

上最后一个顶点，具有

dist (y, z_{1}) < dist (y, u)

，我们有

z_{1} \in Ball (y)

。设

z_{2}

为路径上的下一个顶点，则

dist (y, z_{2}) \geq dist (y, u)

，

so dist (z_{2}, v) = dist (y, v) - dist (y, z_{2}) \leq

dist (y, v) - dist (y, u) < dist (u_{t}, v)

，即

z_{2} \in Ball (v)

。（如果

z_{2}

不存在，则

z_{1} = v

。）根据归纳假设的性质 3，

d (x) = dist (s, x)

在

j

-次迭代的第 1 步之后，因此

d (z_{1})

在

j

-次迭代的第 17 行更新为

dist (s, z_{1})

。因此，

d (v)

在

t

-次迭代的第 12 行更新为

dist (s, v)

（因为

j < t

），与假设相矛盾。

Therefore

d (v) = dist (s, v)

for all

v \in Bundle (u_{t})

after Step 1 of

t

-th iteration.
因此

d (v) = dist (s, v)

对于所有

v \in Bundle (u_{t})

在第

t

次迭代的第 1 步之后。

Remark 2. Pettie and Ramachandran [25] proved that, any hierarchy-based SSSP algorithm on undirected graphs in comparison-addition model takes time at least

Ω (m + min {n \log \log r, n \log n})

, where

r

is the ratio of the maximum-to-minimum edge weight. This bound becomes

Ω (m + n \log n)

when

r

is exponentially large. Here the hierarchy-based algorithm is defined to generate a permutation

π_{s}

satisfying hierarchy property:

dist (s, v) \geq dist (s, u) + sep (u, v) \Rightarrow π_{s} (u) < π_{s} (v)

, where

sep (u, v)

is the longest edge on the MST path between

u

and

v

. The permutation

π_{s}

is, though not defined to be, typically for the algorithms discussed in [25], the order that the algorithm visits the vertices. However, that is a worst-case lower bound, and our algorithm is randomized. Also the order that our algorithm visits the vertices does not follow the hierarchy property: think of two vertices

x

and

y

are both connected to

u

by edges

(x, u), (y, u)

both with weight 1 , and

x, y

are both bundled to

u

. It is possible that

sep (x, y) = 1

and

dist (s, y) = dist (s, x) + 2

but we set no limit on the order we visit

x

and

y

, that it is possible we visit

y

before

x

. This explains why our algorithm can break this

Ω (m + n \log n)

lower bound in [25].
备注 2。Pettie 和 Ramachandran [25] 证明了，在比较-加法模型下，任何基于层次的 SSSP 算法在无向图上至少需要时间

Ω (m + min {n \log \log r, n \log n})

，其中

r

是最大边权与最小边权的比率。当

r

呈指数级增长时，这个界限变为

Ω (m + n \log n)

。这里，基于层次的算法被定义为生成一个满足层次属性的排列

π_{s}

：

dist (s, v) \geq dist (s, u) + sep (u, v) \Rightarrow π_{s} (u) < π_{s} (v)

，其中

sep (u, v)

是

u

和

v

之间 MST 路径上的最长边。排列

π_{s}

虽然没有被定义为，但通常对于[25]中讨论的算法来说，是算法访问顶点的顺序。然而，这只是一个最坏情况的下界，而我们的算法是随机的。此外，我们的算法访问顶点的顺序并不遵循层次属性：考虑两个顶点

x

和

y

都通过边

(x, u), (y, u)

与权重为 1 的

u

相连，并且

x, y

都捆绑到

u

。可能存在

sep (x, y) = 1

和

dist (s, y) = dist (s, x) + 2

，但我们对访问

x

和

y

的顺序没有限制，因此我们可能在访问

y

之前访问

x

。这解释了为什么我们的算法可以打破[25]中的这个

Ω (m + n \log n)

下界。

4 Improved Bundle Construction
4 改进的捆绑构建

In this section we propose an improved bundle construction that runs in

O (m \sqrt{\log n \cdot \log \log n})

time with high probability. In Section 3.3 we showed that correctness of Bundle Dijkstra does
在本节中，我们提出了一种改进的束构造方法，其在高概率下以

O (m \sqrt{\log n \cdot \log \log n})

时间运行。在第 3.3 节中，我们展示了束 Dijkstra 的正确性。
not depend on the choice of

R

, as long as

b (\cdot), Ball (\cdot)

and Bundle

(\cdot)

are correctly computed with respect to

R

. The running time for the bundle construction is

O (\sum_{v \in V ∖ R} | S_{v} | \log | S_{v} |)

, and Bundle Dijkstra is

O (\sum_{v \in V ∖ R} | Ball (v) | + | R | \log n)

.
不依赖于

R

的选择，只要

b (\cdot), Ball (\cdot)

和 Bundle

(\cdot)

相对于

R

正确计算。捆绑构建的运行时间为

O (\sum_{v \in V ∖ R} | S_{v} | \log | S_{v} |)

，Bundle Dijkstra 为

O (\sum_{v \in V ∖ R} | Ball (v) | + | R | \log n)

。

Naturally,

| S_{v} |

is a random variable following geometric distribution for each vertex

v \in V

, and they are not independent since a vertex

x \in V

may appear in several sets. However, for a subset

W \subseteq V

, if any vertex appears at most once in

{S_{v}}_{v \in W}

, the corresponding random variables

{| S_{v} |}_{v \in W}

are independent. By Lemma 9, if each random variable is dependent to few other variables, their summation deviates from the expectation with exponentially small probability. So we manually include all those vertices with

| S_{v} | \geq k \log k

into

R

. In this way for each vertex in

V ∖ R

, its random variable is dependent to only a limited number of other ones, and we can bound their summation with high probability.
自然地，

| S_{v} |

是一个遵循几何分布的随机变量，适用于每个顶点

v \in V

，并且它们不是独立的，因为一个顶点

x \in V

可能出现在多个集合中。然而，对于一个子集

W \subseteq V

，如果任何顶点在

{S_{v}}_{v \in W}

中最多出现一次，则相应的随机变量

{| S_{v} |}_{v \in W}

是独立的。根据引理 9，如果每个随机变量仅依赖于少数其他变量，则它们的总和以指数级小的概率偏离期望。因此，我们手动将所有这些带有

| S_{v} | \geq k \log k

的顶点包含到

R

中。通过这种方式，对于

V ∖ R

中的每个顶点，其随机变量仅依赖于有限数量的其他变量，我们可以以高概率界定它们的总和。

We introduce how to generate

R

and compute

{b (v)}_{v \in V ∖ R}

below, as well as

{Ball (v)}_{v \in V ∖ R}

{Bundle (u)}_{u \in R}

and

dist (v, u)

for

u \in Ball (v) \cup {b (v)}

. The pseudocode is given in Algorithm 2. We still set parameter

k = \sqrt{\frac{\log n}{\log \log n}}

as in Section 3.
我们在下面介绍如何生成

R

和计算

{b (v)}_{v \in V ∖ R}

，以及

{Ball (v)}_{v \in V ∖ R}

、

{Bundle (u)}_{u \in R}

和

dist (v, u)

用于

u \in Ball (v) \cup {b (v)}

。伪代码在算法 2 中给出。我们仍然将参数

k = \sqrt{\frac{\log n}{\log \log n}}

设置为第 3 节中的值。

Improved Bundle Construction.
改进的捆绑构建。

Sample each vertex $v \in V ∖ {s}$ with probability $\frac{1}{k}$ to form set $R_{1}$ and add $s$ into $R_{1}$ ;
以概率 $\frac{1}{k}$ 对每个顶点 $v \in V ∖ {s}$ 进行采样，以形成集合 $R_{1}$ 并将 $s$ 添加到 $R_{1}$ 中；
For each $v \in V ∖ R_{1}$ , run Dijkstra algorithm started from $v$ , until we have extracted a vertex in $R_{1}$ ; or have already popped $k \log k$ vertices.
对于每个 $v \in V ∖ R_{1}$ ，从 $v$ 开始运行 Dijkstra 算法，直到我们提取了 $R_{1}$ 中的一个顶点；或者已经弹出了 $k \log k$ 个顶点。
In the former case, denote the extracted vertices in the order they appeared as list $V_{extract}^{(v)}$ . Note that $V_{extract}^{(v)}$ is similar to $S_{v}$ of Section 3. In the latter case, add $v$ into $R_{2}$ ;
在前一种情况下，按出现顺序将提取的顶点表示为列表 $V_{extract}^{(v)}$ 。注意 $V_{extract}^{(v)}$ 类似于第 3 节的 $S_{v}$ 。在后一种情况下，将 $v$ 添加到 $R_{2}$ 中；
Set $R = R_{1} \cup R_{2}$ , and for $v \in V ∖ R$ , let the first vertex in $V_{extract}^{(v)}$ that lies in $R$ be $b (v)$ ;
设置 $R = R_{1} \cup R_{2}$ ，对于 $v \in V ∖ R$ ，让在 $R$ 中位于 $V_{extract}^{(v)}$ 的第一个顶点为 $b (v)$ ；
With the results above, compute $Bundle (u)$ for $u \in R$ , $Ball (v)$ for $v \in V ∖ R$ , and record $dist (v, u)$ for $u \in Ball (v) \cup {b (v)}$ . This step takes linear time.
根据上述结果，计算 $Bundle (u)$ 对于 $u \in R$ ， $Ball (v)$ 对于 $v \in V ∖ R$ ，并记录 $dist (v, u)$ 对于 $u \in Ball (v) \cup {b (v)}$ 。此步骤需要线性时间。

The correctness of this bundle construction follows from the Dijkstra’s algorithm [8]. We only need to analyze

| R |, \sum_{v \in V ∖ R} | Ball (v) |

and its running time. The performance of this improved bundle construction is characterized in Lemma 8 below. By Lemma 8, the bundle construction takes

O (m k \log k)

time, and bundle Dijkstra takes

O (\sum_{v \in V ∖ R} | Ball (v) | + | R | \log n) = O (m k + m \log n / k)

with probability

1 - e^{- Ω (n^{1 - o (1)})}

. Thus the total running time of our algorithm is

O (m k \log k +

m \log n / k) = O (m \sqrt{\log n \cdot \log \log n})

w.h.p. The proof of Lemma 8 is based on Lemma 9 .
这个束构造的正确性来自于 Dijkstra 算法[8]。我们只需要分析

| R |, \sum_{v \in V ∖ R} | Ball (v) |

及其运行时间。这个改进的束构造的性能在下面的引理 8 中进行了描述。根据引理 8，束构造需要

O (m k \log k)

时间，而束 Dijkstra 以概率

1 - e^{- Ω (n^{1 - o (1)})}

需要

O (\sum_{v \in V ∖ R} | Ball (v) | + | R | \log n) = O (m k + m \log n / k)

。因此，我们算法的总运行时间是

O (m k \log k +

m \log n / k) = O (m \sqrt{\log n \cdot \log \log n})

，以高概率成立。引理 8 的证明基于引理 9。

Lemma 8. By running Algorithm 2, with probability

1 - e^{- Ω (n^{1 - o (1)})}

, the following properties hold:
引理 8。通过运行算法 2，概率为

1 - e^{- Ω (n^{1 - o (1)})}

时，以下属性成立：
(a)

| R | = O (\frac{m}{k})

.
(b)

\sum_{v \in V ∖ R} | Ball (v) | = O (m k)

O (m k \log k)

O (m k \log k)

。

Proof. First, each vertex of

V ∖ {s}

is inserted to

R_{1}

independently with probability

\frac{1}{k}

, so by Chernoff bound, with probability

1 - O (e^{- m / k}) = 1 - e^{- Ω (n^{1 - o (1)})}, | R_{1} | = Θ (m / k)

, and meanwhile

m^{'} := | V ∖ R_{1} | = Θ (m)

.
证明。首先，

V ∖ {s}

的每个顶点以概率

\frac{1}{k}

独立地插入到

R_{1}

中，因此根据切尔诺夫界限，以概率

1 - O (e^{- m / k}) = 1 - e^{- Ω (n^{1 - o (1)})}, | R_{1} | = Θ (m / k)

，同时

m^{'} := | V ∖ R_{1} | = Θ (m)

。

For each vertex

v \in V ∖ R_{1}

, define

X_{v} = I [v \in R_{2}]

and

Y_{v} = | V_{extract}^{(v)} |

. Then,

X_{v}

is a Bernoulli random variable,

X_{v} \in [0, 1]

with probability 1 and

E [X_{v}] = {(1 - \frac{1}{k})}^{k \log k} = Θ (\frac{1}{k})

. And

Y_{v}

is a
对于每个顶点

v \in V ∖ R_{1}

，定义

X_{v} = I [v \in R_{2}]

和

Y_{v} = | V_{extract}^{(v)} |

。然后，

X_{v}

是一个伯努利随机变量，

X_{v} \in [0, 1]

的概率为 1 和

E [X_{v}] = {(1 - \frac{1}{k})}^{k \log k} = Θ (\frac{1}{k})

。而

Y_{v}

是一个

Algorithm 2: BundleConstruction \((G, s, k)\)
    Input : A graph \(G=(V, E, w)\), the source vertex \(s \in V\) and parameter \(k\)
    Output: All \(R, \mathrm{~b}(\cdot)\), Ball( \(\cdot\) ), Bundle( \((\cdot)\) as described above
    Initialize \(R_{1} \leftarrow\{s\}\), and insert each \(v \in V \backslash\{s\}\) to \(R_{1}\) independently with probability \(\frac{1}{k}\);
    Initialize \(R_{2} \leftarrow \emptyset\);
    foreach \(v \in V \backslash R_{1}\) do // Truncated Dijkstra
        Initialize Fibonacci heap \(H^{(v)}\) with vertex \(v\) and its key \(d^{(v)}(v) \leftarrow 0\);
        Initialize an ordered list \(V_{\text {extract }}^{(v)} \leftarrow()\);
        while \(H^{(v)}\) is not empty do
            \(u \leftarrow H\).ExtractMin();
                \(V_{\text {extract }}^{(v)} \cdot \operatorname{APPEND}(u) ;\)
                if \(u \in R_{1}\) then quit the while-loop;
                    else if \(\left|V_{\text {extract }}^{(v)}\right|>k \log k\) then set \(R_{2} \leftarrow R_{2} \cup\{v\}\) and quit the while-loop;
                else
                    foreach \(x \in N(u)\) do
                        if \(x \notin H^{(v)}\) and \(x \notin V_{\text {extract }}^{(v)}\) then \(H^{(v)} \cdot \operatorname{Insert}\left(x, d^{(v)}(u)+w_{u x}\right)\);
                        else if \(d^{(v)}(x)>d^{(v)}(u)+w_{u x}\) then \(H\).DecreaseKey \(\left(x, d^{(v)}(u)+w_{u x}\right)\);
    \(R \leftarrow R_{1} \cup R_{2} ;\)
    foreach \(v \in V \backslash R\) do
        \(\mathrm{b}(v) \leftarrow\) the first vertex in the ordered list \(V_{\text {extract }}^{(v)}\) that lies in \(R\);
    Compute \(\{\operatorname{Bundle}(u)\}_{u \in R},\{\operatorname{Ball}(v)\}_{v \in V \backslash R}\) and record \(\operatorname{dist}(v, u)\) for \(u \in \operatorname{Ball}(v) \cup\{\mathrm{b}(v)\}\);

geometric random variable except its value is zero when

X_{v} = 1

, so

Y_{v} \in [0, k \log k]

with probability 1 and

E [Y_{v}] = k - (k + k \log k) {(1 - \frac{1}{k})}^{k \log k} = Θ (k) .^{2}

几何随机变量，除了在

X_{v} = 1

时其值为零，因此

Y_{v} \in [0, k \log k]

的概率为 1 和

E [Y_{v}] = k - (k + k \log k) {(1 - \frac{1}{k})}^{k \log k} = Θ (k) .^{2}

For each vertex

v \in V ∖ R_{1}

, denote

V_{full}^{(v)}

as the first

k \log k

vertices extracted in the Dijkstra algorithm if it did not truncate. They are determined by the structure of

G

, so there is no randomness in

V_{full}^{(v)}

. The values of

X_{v}

and

Y_{v}

are determined by whether vertices in

V_{full}^{(v)}

were inserted into

R_{1}

. Therefore, if

V_{f u l l}^{(v_{1})}, V_{full}^{(v_{2})}, \dots, V_{full}^{(v_{j})}

are disjoint, then

X_{v_{1}}, X_{v_{2}}, \dots, X_{v_{j}}

are independent, and similarly,

Y_{v_{1}}, Y_{v_{2}}, \dots, Y_{v_{j}}

are independent.
对于每个顶点

v \in V ∖ R_{1}

，如果 Dijkstra 算法没有截断，则将

V_{full}^{(v)}

表示为提取的前

k \log k

个顶点。它们由

G

的结构决定，因此在

V_{full}^{(v)}

中没有随机性。

X_{v}

和

Y_{v}

的值由

V_{full}^{(v)}

中的顶点是否被插入到

R_{1}

中决定。因此，如果

V_{f u l l}^{(v_{1})}, V_{full}^{(v_{2})}, \dots, V_{full}^{(v_{j})}

是不相交的，则

X_{v_{1}}, X_{v_{2}}, \dots, X_{v_{j}}

是独立的，类似地，

Y_{v_{1}}, Y_{v_{2}}, \dots, Y_{v_{j}}

是独立的。

For each vertex

w \in V_{f u l l}^{(v)}

, because

w

is found by

v

within

k \log k

steps of Dijkstra’s algorithm, there must exist a path from

v

w

of no more than

k \log k

edges, so by constant degree property, there are at most

3 \cdot (1 + 2 + \dots + 2^{k \log k - 1}) \leq 3 \cdot 2^{k \log k}

different

u

such that

w \in V_{full}^{(u)}

. Hence, for each

v

, there are at most

3 k \log k \cdot 2^{k \log k} = O (n^{o (1)})

different

u \in V ∖ R_{1}

such that

V_{full}^{(v)} \cap V_{full}^{(u)} \neq \emptyset

.
对于每个顶点

w \in V_{f u l l}^{(v)}

，因为

w

是通过

v

在 Dijkstra 算法的

k \log k

步内找到的，从

v

到

w

必须存在一条不超过

k \log k

条边的路径，因此根据常数度性质，最多有

3 \cdot (1 + 2 + \dots + 2^{k \log k - 1}) \leq 3 \cdot 2^{k \log k}

个不同的

u

使得

w \in V_{full}^{(u)}

。因此，对于每个

v

，最多有

3 k \log k \cdot 2^{k \log k} = O (n^{o (1)})

个不同的

u \in V ∖ R_{1}

使得

V_{full}^{(v)} \cap V_{full}^{(u)} \neq \emptyset

。

To apply Lemma 9, for each

v \in R_{1}

, also define

X_{v}, Y_{v}

and

V_{f u l l}^{(v)}

in the same way as if

v

is executed in the loop of Algorithm 2.
为了应用引理 9，对于每个

v \in R_{1}

，还要以与在算法 2 的循环中执行

v

相同的方式定义

X_{v}, Y_{v}

和

V_{f u l l}^{(v)}

。

Now, we apply Lemma 9 for

{X_{v}}_{v \in V}

and

{Y_{v}}_{v \in V}

. For

{X_{v}}_{v \in V}, S

V

and

| V | = m, μ =

Θ (\frac{1}{k}), b = 1, T = O (n^{o (1)})

, and

{W_{v}}_{v \in V}

are

{V_{f u l l}^{(v)}}_{v \in V}

, and we can verify that

8 T b μ^{- 1} = O (n^{o (1)})

and

8 b^{3} T / μ^{3} = O (n^{o (1)})

, so with probability at least

1 - e^{- Ω (m / n^{o (1)})}

, it holds that

\sum_{v \in S} X_{v} =

现在，我们对

{X_{v}}_{v \in V}

和

{Y_{v}}_{v \in V}

应用引理 9。对于

{X_{v}}_{v \in V}, S

是

V

和

| V | = m, μ =

Θ (\frac{1}{k}), b = 1, T = O (n^{o (1)})

，而

{W_{v}}_{v \in V}

是

{V_{f u l l}^{(v)}}_{v \in V}

，我们可以验证

8 T b μ^{- 1} = O (n^{o (1)})

和

8 b^{3} T / μ^{3} = O (n^{o (1)})

，因此以至少

1 - e^{- Ω (m / n^{o (1)})}

的概率，成立

\sum_{v \in S} X_{v} =

。

Θ (m / k)

. And for

{Y_{v}}_{v \in V}, S

V, μ = Θ (k), b = k \log k, T = O (n^{o (1)})

, and

{W_{v}}_{v \in V}

are also

{V_{f u l l}^{(v)}}_{v \in V}

, and similarly we infer that with probability

1 - e^{- Ω (m / n^{o (1)})}

, it holds that

\sum_{v \in S} Y_{v} =

Θ (m k)

. Thus, we conclude that with probability

1 - e^{- Ω (n^{1 - o (1)})}, \sum_{v \in V ∖ R_{1}} X_{v} = Θ (m / k)

and

\sum_{v \in V ∖ R_{1}} Y_{v} = Θ (m k)

Θ (m / k)

。对于

{Y_{v}}_{v \in V}, S

，

V, μ = Θ (k), b = k \log k, T = O (n^{o (1)})

是，

{W_{v}}_{v \in V}

也

{V_{f u l l}^{(v)}}_{v \in V}

，同样我们推断出以概率

1 - e^{- Ω (m / n^{o (1)})}

，成立的是

\sum_{v \in S} Y_{v} =

Θ (m k)

。因此，我们得出结论，以概率

1 - e^{- Ω (n^{1 - o (1)})}, \sum_{v \in V ∖ R_{1}} X_{v} = Θ (m / k)

和

\sum_{v \in V ∖ R_{1}} Y_{v} = Θ (m k)

。

Then, we prove the three claims of this lemma.
然后，我们证明这个引理的三个主张。
For (a), by definition

| R | = | R_{1} | + | R_{2} |

, so by union bound, with probability

1 - e^{- Ω (n^{1 - o (1)})}

| R | = | R_{1} | + \sum_{v \in V ∖ R_{1}} X_{v} = O (\frac{m}{k})

.
对于 (a)，根据定义

| R | = | R_{1} | + | R_{2} |

，因此根据并集界限，以概率

1 - e^{- Ω (n^{1 - o (1)})}

，

| R | = | R_{1} | + \sum_{v \in V ∖ R_{1}} X_{v} = O (\frac{m}{k})

。

For (b), by definition

| Ball (v) | \leq Y_{v}

, so

\sum_{v \in V ∖ R} | Ball (v) | \leq \sum_{v \in V ∖ R_{1}} Y_{v}

. Thus, with probability

1 - e^{- Ω (n^{1 - o (1)})}, \sum_{v \in V ∖ R} | Ball (v) | = O (m k)

.
对于 (b)，根据定义

| Ball (v) | \leq Y_{v}

，所以

\sum_{v \in V ∖ R} | Ball (v) | \leq \sum_{v \in V ∖ R_{1}} Y_{v}

。因此，概率为

1 - e^{- Ω (n^{1 - o (1)})}, \sum_{v \in V ∖ R} | Ball (v) | = O (m k)

。

v \in V ∖ R_{1}

, by constant degree property, the number of Insert operations is

O (Y_{v})

, so

| H^{(v)} | = O (Y_{v}) = O (k \log k)

. Therefore, each ExtractMin operation takes time

O (\log (Y_{v})) =

O (\log k)

, and every other operation takes constant time. Thus the truncated Dijkstra algorithm of

v

takes time

O (Y_{v} \log k)

. Thus, with probability

1 - e^{- Ω (n^{1 - o (1)})}

, the total time of Algorithm 2 is

O (\sum_{v \in V ∖ R_{1}} Y_{v} \log k) = O (m k \log k)

v \in V ∖ R_{1}

，根据常数度性质，插入操作的数量为

O (Y_{v})

，所以

| H^{(v)} | = O (Y_{v}) = O (k \log k)

。因此，每个 ExtractMin 操作的时间为

O (\log (Y_{v})) =

O (\log k)

，而其他每个操作的时间为常数时间。因此，

v

的截断 Dijkstra 算法的时间为

O (Y_{v} \log k)

。因此，以概率

1 - e^{- Ω (n^{1 - o (1)})}

，算法 2 的总时间为

O (\sum_{v \in V ∖ R_{1}} Y_{v} \log k) = O (m k \log k)

。

Lemma 9. (Similar arguments as in [21]) Suppose a set of random variables

{Z_{v}}_{v \in S}

satisfy that for each

v \in S, E [Z_{v}] = μ, Z_{v} \in [0, b]

with probability 1 , and each

Z_{v}

is corresponded to a fixed deterministic set

W_{v}

such that, if

W_{v_{1}}, W_{v_{2}}, \dots, W_{v_{j}}

are disjoint, then

Z_{v_{1}}, Z_{v_{2}}, \dots, Z_{v_{j}}

are independent, and

W_{v}

intersects with at most

T

different other

W_{u}

.
引理 9. （与 [21] 中的类似论证）假设一组随机变量

{Z_{v}}_{v \in S}

满足对于每个

v \in S, E [Z_{v}] = μ, Z_{v} \in [0, b]

的概率为 1，并且每个

Z_{v}

对应于一个固定的确定性集合

W_{v}

，使得如果

W_{v_{1}}, W_{v_{2}}, \dots, W_{v_{j}}

是不相交的，则

Z_{v_{1}}, Z_{v_{2}}, \dots, Z_{v_{j}}

是独立的，并且

W_{v}

至多与

T

个不同的其他

W_{u}

相交。

Then, with probability at least

1 - 8 T b μ^{- 1} \cdot e^{- \frac{μ^{3} ∣ S S}{8 b^{3} T}}

, it holds that

\sum_{v \in S} Z_{v} = Θ (| S | μ)

.
然后，概率至少为

1 - 8 T b μ^{- 1} \cdot e^{- \frac{μ^{3} ∣ S S}{8 b^{3} T}}

时，成立

\sum_{v \in S} Z_{v} = Θ (| S | μ)

。
Proof. We try to partition

{Z_{v}}_{v \in S}

into several subsets

{Z_{t}}

such that all

Z_{v}

's in each

Z_{t}

are independent so that we can apply Hoeffding’s inequality, or the size of

Z_{t}

is small so that we can bound them by the upper bound

b

, and finally combine everything by the union bound. Also note that we do not need to actually compute

{Z_{t}}

, as they are merely introduced for this mathematical proof.
证明。我们尝试将

{Z_{v}}_{v \in S}

划分为几个子集

{Z_{t}}

，使得每个

Z_{t}

中的所有

Z_{v}

都是独立的，以便我们可以应用 Hoeffding 不等式，或者

Z_{t}

的大小很小，以便我们可以用上界

b

来界定它们，最后通过并集界限将所有内容结合起来。还要注意，我们实际上不需要计算

{Z_{t}}

，因为它们仅仅是为了这个数学证明而引入的。

Fix parameter

p = \frac{| S | μ}{4 T b}

. Since each

W_{v}

intersects with at most

T

different other

W_{u}

, whenever there are at least

p (T + 1)

elements in

{Z_{v}}_{v \in S}

, we can pick

p

different

Z_{v}

from them whose

W_{v}

are disjoint, so that they are independent: pick an arbitrary

Z_{v}

and discard those

Z_{u}

W_{u} \cap W_{v} \neq \emptyset

; since there are at most

T

such

Z_{u}

different from

Z_{v}

, every time we discard at most

T + 1

elements. So from

p (T + 1)

elements we can pick

p

of them. We let them form a

Z_{t}

and remove them from

{Z_{v}}_{v \in S}

. Repeating this process we will end up with a partition

{Z_{1}, Z_{2}, \dots, Z_{q}, Z_{q + 1}}

{Z_{v}}_{v \in S}

such that:

| Z_{t} | = p

, and all

Z_{v} \in Z_{t}

are independent for

1 \leq t \leq q; | Z_{q + 1} | \leq p (T + 1) \leq 2 p T = \frac{μ}{2 b} | S |

. By definition

μ \leq b

, so

| Z_{q + 1} | \leq \frac{1}{2} | S |

.
修复参数

p = \frac{| S | μ}{4 T b}

。由于每个

W_{v}

至多与

T

个不同的其他

W_{u}

相交，只要在

{Z_{v}}_{v \in S}

中至少有

p (T + 1)

个元素，我们就可以从中选择

p

个不同的

Z_{v}

，它们的

W_{v}

是不相交的，从而使它们是独立的：选择一个任意的

Z_{v}

，并在

W_{u} \cap W_{v} \neq \emptyset

时丢弃那些

Z_{u}

；由于至多有

T

个这样的

Z_{u}

与

Z_{v}

不同，每次我们最多丢弃

T + 1

个元素。因此，从

p (T + 1)

个元素中我们可以选择

p

个。我们让它们形成一个

Z_{t}

并将它们从

{Z_{v}}_{v \in S}

中移除。重复这个过程，我们将得到一个

{Z_{1}, Z_{2}, \dots, Z_{q}, Z_{q + 1}}

的划分，划分为

{Z_{v}}_{v \in S}

，使得：

| Z_{t} | = p

，并且所有

Z_{v} \in Z_{t}

对于

1 \leq t \leq q; | Z_{q + 1} | \leq p (T + 1) \leq 2 p T = \frac{μ}{2 b} | S |

是独立的。根据定义

μ \leq b

，所以

| Z_{q + 1} | \leq \frac{1}{2} | S |

。

Then by Hoeffding’s inequality, for each

1 \leq t \leq q

,
然后根据霍夫丁不等式，对于每个

1 \leq t \leq q

，

\Pr [| \sum_{v \in Z_{t}} Z_{v} - | Z_{t} | μ | \geq \frac{1}{2} | Z_{t} | μ] \leq 2 e^{- \frac{2 {(\frac{1}{2} | Z_{t} | μ)}^{2}}{| Z_{t} | b^{2}}} = 2 e^{- \frac{μ^{2} p}{2 b^{2}}} .

and

0 \leq \sum_{v \in Z_{q + 1}} Z_{v} \leq | Z_{q + 1} | b

with probability 1 .
和

0 \leq \sum_{v \in Z_{q + 1}} Z_{v} \leq | Z_{q + 1} | b

的概率为 1。
By union bound, with probability at least

1 - 2 q e^{- \frac{μ^{2} p}{2 b^{2}}}

,
根据联合界限，概率至少为

1 - 2 q e^{- \frac{μ^{2} p}{2 b^{2}}}

，

\sum_{v \in S} Z_{v} \geq \frac{1}{2} \sum_{t = 1}^{q} | Z_{t} | μ = \frac{1}{2} (| S | - | Z_{q + 1} |) μ \geq \frac{1}{2} (| S | - \frac{1}{2} | S |) μ = \frac{1}{4} | S | μ,

and meanwhile 同时

\sum_{v \in S} Z_{v} \leq \frac{3}{2} \sum_{t = 1}^{q} | Z_{t} | μ + | Z_{q + 1} | b \leq \frac{3}{2} | S | μ + \frac{μ}{2 b} | S | \cdot b = 2 | S | μ

And from

| S | \geq \sum_{t = 1}^{q} | Z_{t} | \geq q p

, we conclude that

q \leq | S | / p = 4 T b / μ

. Thus, with probability at least

1 - 8 T b μ^{- 1} e^{- \frac{μ^{3} | S |}{8 b^{3} T}}

, it holds that

\sum_{v \in S} Z_{v} = Θ (| S | μ)

.
因此，从

| S | \geq \sum_{t = 1}^{q} | Z_{t} | \geq q p

我们得出结论

q \leq | S | / p = 4 T b / μ

。因此，至少以

1 - 8 T b μ^{- 1} e^{- \frac{μ^{3} | S |}{8 b^{3} T}}

的概率，成立

\sum_{v \in S} Z_{v} = Θ (| S | μ)

。

5 Discussion 5 讨论

We gratefully acknowledge an anonymous reviewer for suggesting that constant-degree is not a necessary condition for this algorithm, so we can get improved time complexity when

m = ω (n)

and

m = o (n \log n)

. Instead of making the graph of degree 3, we use similar methods to split the vertices of degree

> m / n

to vertices of degrees

\leq m / n

, so that the number of vertices is still

O (n)

. Then in each step:
我们衷心感谢一位匿名评审提出常数度不是该算法的必要条件，因此我们可以在

m = ω (n)

和

m = o (n \log n)

时获得更好的时间复杂度。我们不再将图的度数设为 3，而是使用类似的方法将度数为

> m / n

的顶点拆分为度数为

\leq m / n

的顶点，从而顶点的数量仍然是

O (n)

。然后在每一步：

In bundle construction, the time for Dijkstra search for every vertex $v$ will become $O (| S_{v} | \cdot \frac{m}{n} +$ $| S_{v} | \log (| S_{v} | \cdot \frac{m}{n}))$ , since the size of the heap is at most $| S_{v} | \cdot \frac{m}{n}$ , so in total $O (m k + n k \log (m k / n))$ .
在捆绑构建中，每个顶点 $v$ 的 Dijkstra 搜索时间将变为 $O (| S_{v} | \cdot \frac{m}{n} +$ $| S_{v} | \log (| S_{v} | \cdot \frac{m}{n}))$ ，因为堆的大小最多为 $| S_{v} | \cdot \frac{m}{n}$ ，所以总共为 $O (m k + n k \log (m k / n))$ 。
The time for Bundle Dijkstra will become $O (\frac{n}{k} \log n + m k)$ , since the number of vertices $z_{1}$ in Step 1 for every $v$ is $O (\frac{m}{n} | Ball (v) |)$ , and the number of vertices $z_{1}$ in Step 2 for every $y$ is $O (| Ball (y) |)$ but each vertex appears $O (m / n)$ times as $y$ in Step 2 .
Bundle Dijkstra 的时间将变为 $O (\frac{n}{k} \log n + m k)$ ，因为每个 $v$ 在步骤 1 中的顶点数量 $z_{1}$ 为 $O (\frac{m}{n} | Ball (v) |)$ ，而每个 $y$ 在步骤 2 中的顶点数量 $z_{1}$ 为 $O (| Ball (y) |)$ ，但每个顶点在步骤 2 中出现了 $O (m / n)$ 次，作为 $y$ 。
When $m / n = o (\log n)$ , one can check that the analysis of independence in Section 4 still works, since the number of different $u \in V ∖ R_{1}$ which have $V_{full}^{(v)} \cap V_{full}^{(u)} \neq \emptyset$ for each $v \in V ∖ R_{1}$ is still $O (n^{o (1)})$ .
当 $m / n = o (\log n)$ 时，可以检查第 4 节中的独立性分析仍然有效，因为对于每个 $v \in V ∖ R_{1}$ ，具有 $V_{full}^{(v)} \cap V_{full}^{(u)} \neq \emptyset$ 的不同 $u \in V ∖ R_{1}$ 的数量仍然是 $O (n^{o (1)})$ 。
Thus, the time complexity for this algorithm is $O (\frac{n}{k} \log n + m k + n k \log (m k / n))$ . When $m < n \log \log n, k$ still equals to $\sqrt{\frac{\log n}{\log \log n}}$ , and the time bound is $O (n \sqrt{\log n \log \log n})$ . When $n \log \log n \leq m < n \log n$ , let $k = \sqrt{\frac{n}{m} \log n}$ , and the time bound will be $O (\sqrt{m n \log n})$ .
因此，该算法的时间复杂度为 $O (\frac{n}{k} \log n + m k + n k \log (m k / n))$ 。当 $m < n \log \log n, k$ 仍然等于 $\sqrt{\frac{\log n}{\log \log n}}$ 时，时间界限为 $O (n \sqrt{\log n \log \log n})$ 。当 $n \log \log n \leq m < n \log n$ 时，设 $k = \sqrt{\frac{n}{m} \log n}$ ，时间界限将为 $O (\sqrt{m n \log n})$ 。

References 参考文献

[1] D. Aingworth, C. Chekuri, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '96, page 547-553, USA, 1996. Society for Industrial and Applied Mathematics. ISBN 0898713668.
[1] D. Aingworth, C. Chekuri, 和 R. Motwani. 快速估计直径和最短路径（不使用矩阵乘法）。在第七届年度 ACM-SIAM 离散算法研讨会论文集，SODA '96，第 547-553 页，美国，1996 年。工业与应用数学学会。ISBN 0898713668。
[2] Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight singlesource shortest paths in near-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 600-611, 2022. doi: 10.1109/FOCS54457.2022. 00063.
[2] Aaron Bernstein, Danupon Nanongkai, 和 Christian Wulff-Nilsen. 近线性时间内的负权单源最短路径. 在 2022 年 IEEE 第 63 届计算机科学基础年会（FOCS）上，页码 600-611，2022 年。doi: 10.1109/FOCS54457.2022. 00063.
[3] Timothy M. Chan. All-pairs shortest paths with real weights in

O (n^{3} / \log n)

time. Algorithmica, 50(2):236-243, 2008. doi: 10.1007/s00453-007-9062-1. URL https://doi.org/10.1007/s00453-007-9062-1.
[3] Timothy M. Chan. 在

O (n^{3} / \log n)

时间内处理具有实数权重的所有对最短路径。Algorithmica, 50(2):236-243, 2008. doi: 10.1007/s00453-007-9062-1. URL https://doi.org/10.1007/s00453-007-9062-1.
[4] Bernard Chazelle. A minimum spanning tree algorithm with inverse-ackermann type complexity. J.

A C M, 47 (6) : 1028 - 1047

, nov 2000. ISSN 0004-5411. doi: 10.1145/355541.355562. URL https://doi.org/10.1145/355541.355562.
[4] Bernard Chazelle. 一种具有逆阿克曼类型复杂度的最小生成树算法。J.

A C M, 47 (6) : 1028 - 1047

, 2000 年 11 月。ISSN 0004-5411。doi: 10.1145/355541.355562。网址 https://doi.org/10.1145/355541.355562。
[5] Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck paths and trees and deterministic graphical games. In Nicolas Ollinger and Heribert Vollmer, editors, STACS, volume 47 of LIPIcs, pages 27:1-27:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. ISBN 978-3-95977-001-9. URL http://dblp.uni-trier.de/db/conf/stacs/stacs2016.html#ChechikKTZZ16.
[5] Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, 和 Uri Zwick. 瓶颈路径和树以及确定性图形游戏. 在 Nicolas Ollinger 和 Heribert Vollmer, 编辑, STACS, LIPIcs 第 47 卷, 页码 27:1-27:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. ISBN 978-3-95977-001-9. URL http://dblp.uni-trier.de/db/conf/stacs/stacs2016.html#ChechikKTZZ16.
[6] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623, 2022. doi: 10.1109/FOCS54457.2022.00064.
[6] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, 和 Sushant Sachdeva. 几乎线性时间内的最大流和最小成本流. 在 2022 年 IEEE 第 63 届计算机科学基础年会（FOCS）上，页面 612-623，2022. doi: 10.1109/FOCS54457.2022.00064.
[7] Andrew Chi chih Yao. An

O (| E | \log \log | V |)

algorithm for finding minimum spanning trees. Information Processing Letters, 4(1):21-23, 1975. ISSN 0020-0190. doi: https://doi.org/10.1016/0020-0190(75)90056-3. URL https://www.sciencedirect.com/science/article/pii/0020019075900563.
[7] Andrew Chi chih Yao. 一种

O (| E | \log \log | V |)

算法用于寻找最小生成树。信息处理快报，4(1):21-23, 1975。ISSN 0020-0190。doi: https://doi.org/10.1016/0020-0190(75)90056-3。URL https://www.sciencedirect.com/science/article/pii/0020019075900563。
[8] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
[8] E. W. Dijkstra. 关于图的两个问题的说明。数值数学, 1:269-271, 1959.
[9] Wlodzimierz Dobosiewicz. A more efficient algorithm for the min-plus multiplication. International Journal of Computer Mathematics, 32(1-2):49-60, 1990. doi: 10.1080/ 00207169008803814. URL https://doi.org/10.1080/00207169008803814.
[9] Wlodzimierz Dobosiewicz. 一种更高效的最小加法乘法算法。国际计算数学杂志，32(1-2):49-60, 1990. doi: 10.1080/ 00207169008803814. URL https://doi.org/10.1080/00207169008803814.
[10] James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to fibonacci heaps with applications to parallel computation. Commun. ACM, 31(11):1343-1354, nov 1988. ISSN 0001-0782. doi: 10.1145/50087.50096. URL https://doi.org/10.1145/50087.50096.
[10] James R. Driscoll, Harold N. Gabow, Ruth Shrairman, 和 Robert E. Tarjan. 放松堆：一种替代斐波那契堆的方案，应用于并行计算。Commun. ACM, 31(11):1343-1354, 1988 年 11 月。ISSN 0001-0782。doi: 10.1145/50087.50096。URL https://doi.org/10.1145/50087.50096。
[11] Ran Duan, Kaifeng Lyu, Hongxun Wu, and Yuanhang Xie. Single-source bottleneck path algorithm faster than sorting for sparse graphs. CoRR, abs/1808.10658, 2018. URL http://arxiv.org/abs/1808.10658.
[11] Ran Duan, Kaifeng Lyu, Hongxun Wu, 和 Yuanhang Xie. 对于稀疏图，比排序更快的单源瓶颈路径算法. CoRR, abs/1808.10658, 2018. URL http://arxiv.org/abs/1808.10658.
[12] Robert W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5:345, 1962.
[12] 罗伯特·W·弗洛伊德。算法 97：最短路径。《计算机协会通讯》，5:345，1962。
[13] Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, page 252-257, New York, NY, USA, 1983. Association for Computing Machinery. ISBN 0897910990. doi:

10.1145 / 800061.808754

. URL https://doi.org/10.1145/800061.808754.
[13] Greg N. Frederickson. 在线更新最小生成树的数据结构。在第十五届年度 ACM 计算理论研讨会论文集，STOC '83，第 252-257 页，纽约，纽约州，美国，1983 年。计算机协会。ISBN 0897910990。doi:

10.1145 / 800061.808754

。网址 https://doi.org/10.1145/800061.808754。
[14] M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987.
[14] M. L. Fredman 和 R. E. Tarjan. 斐波那契堆及其在改进网络优化算法中的应用. ACM 期刊, 34(3):596-615, 1987.
[15] Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM Journal on Computing, 5(1):83-89, 1976. doi: 10.1137/0205006. URL https://doi.org/10.1137/0205006.
[15] Michael L. Fredman. 最短路径问题复杂度的新界限。SIAM 计算杂志，5(1):83-89, 1976. doi: 10.1137/0205006. URL https://doi.org/10.1137/0205006.
[16] Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424-436, 1993. ISSN 0022-0000. doi: https://doi.org/10.1016/0022-0000(93)90040-4. URL https://www.sciencedirect.com/science/article/pii/0022000093900404.
[16] Michael L. Fredman 和 Dan E. Willard. 超越信息理论界限的融合树. 计算机与系统科学杂志, 47(3):424-436, 1993. ISSN 0022-0000. doi: https://doi.org/10.1016/0022-0000(93)90040-4. URL https://www.sciencedirect.com/science/article/pii/0022000093900404.
[17] Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences, 48(3):533551, 1994. ISSN 0022-0000. doi: https://doi.org/10-1016/S0022-0000(05)80064-9. URL https://www.sciencedirect.com/science/article/pii/S0022000005800649.
[17] Michael L. Fredman 和 Dan E. Willard. 最小生成树和最短路径的跨二分算法. 计算机与系统科学杂志, 48(3):533551, 1994. ISSN 0022-0000. doi: https://doi.org/10-1016/S0022-0000(05)80064-9. URL https://www.sciencedirect.com/science/article/pii/S0022000005800649.
[18] Harold N Gabow and Robert E Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411-417, 1988. ISSN 0196-6774. doi: https://doi.org/10.1016/0196-6774(88)90031-4. URL https://www.sciencedirect.com/science/article/pii/0196677488900314.
[18] Harold N Gabow 和 Robert E Tarjan. 两个瓶颈优化问题的算法. 算法杂志, 9(3):411-417, 1988. ISSN 0196-6774. doi: https://doi.org/10.1016/0196-6774(88)90031-4. URL https://www.sciencedirect.com/science/article/pii/0196677488900314.
[19] Torben Hagerup. Improved shortest paths on the word ram. In Ugo Montanari, José D. P. Rolim, and Emo Welzl, editors, Automata, Languages and Programming, pages 61-72, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. ISBN 978-3-540-45022-1.
[19] Torben Hagerup. 在字内存上改进的最短路径。收录于 Ugo Montanari、José D. P. Rolim 和 Emo Welzl 编辑的《自动机、语言与编程》，第 61-72 页，柏林，海德堡，2000。施普林格柏林海德堡。ISBN 978-3-540-45022-1。
[20] Yijie Han and Tadao Takaoka. An

O (n^{3} \log \log n / \log^{2} n)

time algorithm for all pairs shortest paths. In Proceedings of the 13th Scandinavian Conference on Algorithm Theory, SWAT’12, page 131-141, Berlin, Heidelberg, 2012. Springer-Verlag. ISBN 9783642311543. doi: 10.1007/ 978-3-642-31155-0_12. URL https://doi.org/10.1007/978-3-642-31155-0_12.
[20] Yijie Han 和 Tadao Takaoka. 一种

O (n^{3} \log \log n / \log^{2} n)

时间算法用于所有对的最短路径. 见第 13 届斯堪的纳维亚算法理论会议论文集，SWAT’12，第 131-141 页，柏林，海德堡，2012 年。施普林格-弗拉格。ISBN 9783642311543。doi: 10.1007/ 978-3-642-31155-0_12。网址 https://doi.org/10.1007/978-3-642-31155-0_12。
[21] Svante Janson. Large deviations for sums of partly dependent random variables. Random Struct. Algorithms, 24(3):234-248, may 2004. ISSN 1042-9832.
[21] Svante Janson. 部分依赖随机变量和的巨大偏差。随机结构与算法, 24(3):234-248, 2004 年 5 月。ISSN 1042-9832。
[22] David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42(2):321-328, mar 1995. ISSN 0004-5411. doi: 10.1145/201019.201022. URL https://doi.org/10.1145/201019.201022.
[22] David R. Karger, Philip N. Klein, 和 Robert E. Tarjan. 一种随机线性时间算法用于寻找最小生成树. J. ACM, 42(2):321-328, 1995 年 3 月. ISSN 0004-5411. doi: 10.1145/201019.201022. URL https://doi.org/10.1145/201019.201022.
[23] Seth Pettie. A new approach to all-pairs shortest paths on realweighted graphs. Theoretical Computer Science, 312(1):47-74, 2004. ISSN 0304-3975. doi: https://doi.org/10.1016/S0304-3975(03)00402-X. URL https://www.sciencedirect.com/science/article/pii/S030439750300402X. Automata, Languages and Programming.
[23] Seth Pettie. 一种针对实权重图的全对最短路径的新方法。理论计算机科学，312(1):47-74, 2004。ISSN 0304-3975。doi: https://doi.org/10.1016/S0304-3975(03)00402-X。网址 https://www.sciencedirect.com/science/article/pii/S030439750300402X。自动机、语言与编程。
[24] Seth Pettie and Vijaya Ramachandran. An optimal minimum spanning tree algorithm. J.

A C M, 49 (1) : 16 - 34

, jan 2002. ISSN 0004-5411. doi: 10.1145/505241.505243. URL https://doi.org/10.1145/505241.505243.
[24] Seth Pettie 和 Vijaya Ramachandran. 一种最优的最小生成树算法. J.

A C M, 49 (1) : 16 - 34

, 2002 年 1 月. ISSN 0004-5411. doi: 10.1145/505241.505243. URL https://doi.org/10.1145/505241.505243.
[25] Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM Journal on Computing, 34(6):1398-1431, 2005. doi: 10.1137/ S0097539702419650. URL https://doi.org/10.1137/S0097539702419650.
[25] Seth Pettie 和 Vijaya Ramachandran. 一种用于实权重无向图的最短路径算法. SIAM 计算期刊, 34(6):1398-1431, 2005. doi: 10.1137/S0097539702419650. URL https://doi.org/10.1137/S0097539702419650.
[26] Rajeev Raman. Priority queues: Small, monotone and trans-dichotomous. In Proceedings of the Fourth Annual European Symposium on Algorithms, ESA '96, page 121-137, Berlin, Heidelberg, 1996. Springer-Verlag. ISBN 3540616802.
[26] Rajeev Raman. 优先队列：小型、单调和跨二分的。在第四届年度欧洲算法研讨会论文集，ESA '96，第 121-137 页，柏林，海德堡，1996 年。施普林格- Verlag。ISBN 3540616802。
[27] Rajeev Raman. Recent results on the single-source shortest paths problem. SIGACT News, 28(2):81-87, jun 1997. ISSN 0163-5700. doi: 10.1145/261342.261352. URL https://doi.org/10.1145/261342.261352.
[27] Rajeev Raman. 单源最短路径问题的最新结果。SIGACT News, 28(2):81-87, 1997 年 6 月。ISSN 0163-5700。doi: 10.1145/261342.261352。网址 https://doi.org/10.1145/261342.261352。
[28] Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46(3):362-394, may 1999. ISSN 0004-5411. doi: 10.1145/316542.316548. URL https://doi.org/10.1145/316542.316548.
[28] Mikkel Thorup. 线性时间内带正整数权重的无向单源最短路径. J. ACM, 46(3):362-394, 1999 年 5 月. ISSN 0004-5411. doi: 10.1145/316542.316548. URL https://doi.org/10.1145/316542.316548.
[29] Mikkel Thorup. On ram priority queues. SIAM Journal on Computing, 30(1):86-109, 2000. doi: 10.1137/S0097539795288246. URL https://doi.org/10.1137/S0097539795288246.
[29] Mikkel Thorup. 关于 RAM 优先队列。SIAM 计算期刊，30(1):86-109, 2000. doi: 10.1137/S0097539795288246. URL https://doi.org/10.1137/S0097539795288246.
[30] Mikkel Thorup. Floats, integers, and single source shortest paths. J. Algorithms,

35 (2) : 189 - 201

, may 2000. ISSN 0196-6774. doi: 10.1006/jagm.2000.1080. URL https://doi.org/10.1006/jagm.2000.1080.
[30] Mikkel Thorup. 浮点数、整数和单源最短路径。J. Algorithms,

35 (2) : 189 - 201

, 2000 年 5 月。ISSN 0196-6774。doi: 10.1006/jagm.2000.1080。网址 https://doi.org/10.1006/jagm.2000.1080。
[31] Mikkel Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. Journal of Computer and System Sciences, 69(3): 330-353, 2004. ISSN 0022-0000. doi: https://doi.org/10.1016/j.jcss.2004.04.003. URL https://www.sciencedirect.com/science/article/pii/S002200000400042X. Special Issue on STOC 2003.
[31] Mikkel Thorup. 常数时间内减少键值的整数优先队列与单源最短路径问题。计算机与系统科学杂志, 69(3): 330-353, 2004. ISSN 0022-0000. doi: https://doi.org/10.1016/j.jcss.2004.04.003. URL https://www.sciencedirect.com/science/article/pii/S002200000400042X. STOC 2003 特刊。
[32] Stephen Warshall. A theorem on boolean matrices. J. ACM, 9(1):11-12, jan 1962. ISSN 0004-5411. doi: 10.1145/321105.321107. URL https://doi.org/10.1145/321105. 321107.
[32] 斯蒂芬·沃肖尔。关于布尔矩阵的定理。J. ACM, 9(1):11-12, 1962 年 1 月。ISSN 0004-5411。doi: 10.1145/321105.321107。网址 https://doi.org/10.1145/321105.321107。
[33] Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, page 664-673, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107. doi: 10.1145/2591796.2591811. URL https://doi.org/10.1145/2591796.2591811.
[33] Ryan Williams. 通过电路复杂性加速所有对之间的最短路径。在第四十六届年度 ACM 计算理论研讨会论文集，STOC '14，第 664-673 页，纽约，纽约州，美国，2014 年。计算机协会。ISBN 9781450327107。doi: 10.1145/2591796.2591811。网址 https://doi.org/10.1145/2591796.2591811。
[34] Virginia Vassilevska Williams. Nondecreasing paths in a weighted graph or: How to optimally read a train schedule. ACM Trans. Algorithms, 6(4), sep 2010. ISSN 1549-6325. doi: 10.1145/ 1824777.1824790. URL https://doi.org/10.1145/1824777.1824790.
[34] Virginia Vassilevska Williams. 加权图中的非递减路径或：如何最优地读取火车时刻表。ACM Trans. Algorithms, 6(4), 2010 年 9 月。ISSN 1549-6325。doi: 10.1145/1824777.1824790。网址 https://doi.org/10.1145/1824777.1824790。
[35] Uri Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004. Proceedings, page 921-932, Berlin, Heidelberg, 2004. Springer-Verlag. ISBN 978-3-540-24131-7. doi: 10.1007/978-3-540-30551-4_78. URL https://doi.org/10.1007/978-3-540-30551-4_78.
[35] Uri Zwick. 一种稍微改进的亚立方算法，用于解决具有实际边长的所有对最短路径问题。在算法与计算：第十五届国际研讨会，ISAAC 2004，香港，中国，2004 年 12 月 20-22 日。会议录，第 921-932 页，柏林，海德堡，2004 年。施普林格- Verlag。ISBN 978-3-540-24131-7。doi: 10.1007/978-3-540-30551-4_78。网址 https://doi.org/10.1007/978-3-540-30551-4_78。

*duanran@mail.tsinghua.edu.cn
$^{†}$ mjy22@mails.tsinghua.edu.cn
$^{‡} xkshu @ cs . hku . h k$
§ylh21@mails.tsinghua.edu.cn
$^{1}$ One may notice that sampled set, closest sampled vertex and balls are common techniques in papers on shortest path algorithms, distance oracles and spanners, and there are deterministic construction algorithms for such “dominating set” (e.g. [1]), but the extra $O (\log n)$ factor for deterministic approaches introduced on the size of dominating set or construction time is not affordable here.
$^{1}$ 人们可能会注意到，采样集、最近的采样顶点和球体是关于最短路径算法、距离神谕和支撑器的论文中常见的技术，并且对于这种“主导集”有确定性构造算法（例如 [1]），但在这里引入的关于主导集大小或构造时间的额外 $O (\log n)$ 因素是无法承受的。
$^{2}$ Detailed calculation: $E [Y_{v}] = k - \sum_{i = k \log k + 1}^{+ \infty} \frac{1}{k} {(1 - \frac{1}{k})}^{i - 1} \cdot i = k - {(1 - \frac{1}{k})}^{k \log k} \sum_{i = 1}^{+ \infty} \frac{1}{k} {(1 - \frac{1}{k})}^{i - 1} \cdot (i + k \log k) =$ $k - {(1 - \frac{1}{k})}^{k \log k} (k + k \log k)$ . Noticing that ${(1 - \frac{1}{k})}^{k \log k} \leq 1 / k$ , so $k - 1 - \log k \leq E [Y_{v}] \leq k$ and $E [Y_{v}] = Θ (k)$ .
$^{2}$ 详细计算： $E [Y_{v}] = k - \sum_{i = k \log k + 1}^{+ \infty} \frac{1}{k} {(1 - \frac{1}{k})}^{i - 1} \cdot i = k - {(1 - \frac{1}{k})}^{k \log k} \sum_{i = 1}^{+ \infty} \frac{1}{k} {(1 - \frac{1}{k})}^{i - 1} \cdot (i + k \log k) =$ $k - {(1 - \frac{1}{k})}^{k \log k} (k + k \log k)$ 。注意到 ${(1 - \frac{1}{k})}^{k \log k} \leq 1 / k$ ，所以 $k - 1 - \log k \leq E [Y_{v}] \leq k$ 和 $E [Y_{v}] = Θ (k)$ 。

A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs 无向实权图单源最短路径的随机算法

Abstract 摘要

1 Introduction 1 引言

1.1 Our Results 1.1 我们的结果

1.2 Other Related Works1.2 其他相关工作

2 Preliminaries 2 前言

3 Main Algorithm 3 主算法

3.1 Bundle Construction 3.1 捆绑构建

3.2 Bundle Dijkstra 3.2 捆绑 Dijkstra

3.3 Proof of Correctness3.3 正确性证明

4 Improved Bundle Construction4 改进的捆绑构建

Improved Bundle Construction.改进的捆绑构建。

5 Discussion 5 讨论

References 参考文献

A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
无向实权图单源最短路径的随机算法

1.2 Other Related Works
1.2 其他相关工作

3.3 Proof of Correctness
3.3 正确性证明

4 Improved Bundle Construction
4 改进的捆绑构建

Improved Bundle Construction.
改进的捆绑构建。