当前没有测试数据。

1. 引言

1950年代，Bellman和Ford提出的经典算法能够在含负权边的加权图中计算单源最短路径，其时间复杂度为(O(mn))（(n)为顶点数，(m)为边数）。这一算法至今仍是本科算法课程的标准内容（例如参考[6]）。2023年，在Bellman-Ford算法诞生近70年后，Fineman[8]首次将时间复杂度改进至(\tilde{O}(m n^{8/9}))（(\tilde{O})表示忽略对数因子）。随后，Huang、Jin和Quanrud（来自普渡大学，本文称其为“Boilermakers团队”）进一步优化至(\tilde{O}(m n^{4/5}))。

本文基于上述成果，提出了一种期望时间复杂度为(\tilde{O}(m \sqrt{n}))的算法。我们的核心观察是：通过价格函数（potential function）对降价成本（reduced cost）进行线性时间更新，能够直接优化现有算法。为了达到最终复杂度，我们还设计了Fineman分层结构的递归版本。

1.1 问题背景与模型

本文关注强多项式算法（strongly polynomial algorithm），即仅允许算术运算和比较操作的模型。与之相对，弱多项式算法（weakly polynomial algorithms）允许分桶（bucketing）等操作，并已实现了接近线性的时间复杂度。例如，2022年Bernstein等人[2]提出了(\tilde{O}(m \log C))时间算法（(C)为边权最大值），改进了Goldberg 1995年的(O(m \sqrt{n} \log C))算法[11]。目前，弱多项式模型下的最优算法由Bringmann等人[3]提出。

1.2 算法思想概述

价格函数是解决负权最短路径问题的经典工具（例如Johnson算法[13]）。通过定义价格函数(\phi(v))，边权可转换为降价成本： [ w_{\phi}(u, v) = w(u, v) - \phi(v) + \phi(u). ] 若(\phi)使得所有降价成本非负，则可使用Dijkstra算法高效计算最短路径。

Fineman的核心思想是通过一系列价格函数逐步“中和”（neutralize）负权边。具体而言，若负权边的端点在某种跳距（hop distance）意义下是“远程”（remote）的，则可通过局部Dijkstra计算消除其负权影响。Boilermakers团队进一步引入了“适当跳距”（proper hop distance）的概念，通过随机采样顶点对快速定位负权路径。

本文的创新在于：

1. 递归分层结构：通过多尺度的((\tau, \beta))-图递归限制顶点对间的“中间顶点”数量，将问题分解为更小的子问题。
2. 价格函数的线性更新：利用降价成本的线性时间更新，避免重复计算全局距离。
3. 负权边的远程化处理：通过价格函数将负权边限制在局部子图中，结合Dijkstra和Bellman-Ford迭代高效中和。

关键符号与术语说明

• 跳距（Hop Distance）：(d^h(u, v))表示从(u)到(v)最多使用(h)条负权边的最短路径长度。
• 分层((\tau, \beta))-图：通过随机采样(\tau \log n)个顶点构建二分图，确保任意顶点对的(\beta)-中间顶点数(\leq n/\tau)。
• 负权三明治（Negative Sandwich）：三元组((s, t, N))，其中(N)是位于(s)和(t)之间的负权顶点集合。

2. 预备知识

考虑图 (G = (V, E))，边权为 (w(e))。有效标签（valid labelling）是指对每个顶点 (v) 赋予标签 (d(v))，满足： [ \forall e=(u, v) \in E, \quad d(v) \leq d(u) + w(e). ] 该不等式表明，顶点 (v) 的距离标签不超过其前驱顶点 (u) 的标签加上边权。特别地，若存在源点 (s)，则最短路径距离是满足 (d(s) = 0) 且最大化 (\sum_{u} d(u)) 的有效标签。

2.1 价格函数与降价成本

价格函数（price function）为每个顶点 (v) 分配一个值 (\phi(v))。边 (e = (u, v)) 的降价成本（reduced cost）定义为： [ w_{\phi}(u, v) = w(e) - \phi(v) + \phi(u). ] 若降价成本非负，则称该边被价格函数中和（neutralized）。有效标签 (d(\cdot)) 对应的降价成本恒非负（即 (w_d(e) \geq 0)），因此寻找中和所有边的价格函数等价于寻找有效标签。

2.2 Bellman-Ford与Dijkstra的结合

经典的Bellman-Ford算法通过 (n) 次迭代更新距离标签： [ d(v) = \min(d(v), d(u) + w(u, v)). ] 第 (i) 次迭代后，(d(v)) 表示从源点出发最多使用 (i) 条边的最短路径长度。

Dijkstra算法通过维护一个优先队列，每次选择当前距离最小的顶点 (v) 并更新其邻接顶点。若边权非负，该算法可在 (O(m + n \log n)) 时间内计算最短路径。

Bellman-Ford/Dijkstra迭代的关键观察是：

• 每次Bellman-Ford迭代处理负权边，更新距离标签。
• 随后的Dijkstra迭代确保非负边的降价成本保持非负。
• 经过 (i) 次迭代，(d(v)) 表示从源点出发最多使用 (i) 条负权边的最短路径长度。

2.3 负权顶点与子图构造

负权顶点（negative vertex）是指作为某条负权边起点的顶点。定义子图 (G(S))：

• 若边 (e = (u, v)) 的起点 (u \notin S)，则将其权值设为 (\max(w(e), 0))；
• 否则保留原权值。

为简化分析，假设所有顶点的度数为 (O(m/n))。若存在大度顶点，可通过拆分顶点并添加0权边处理，顶点数仅增加常数倍（见[8]）。

2.4 随机采样与高概率事件

在算法设计中，随机采样和高概率事件是关键工具。以下引理用于分析采样策略：

引理1：对于 (n) 个元素的排列，随机选取大小为 (c \tau \log n) 的子集 (S)，则前 (n/\tau) 个元素中至少有一个被选中的概率 (\geq 1 - 1/n)。
证明：每个元素不在前 (n/\tau) 位置的概率为 (1 - 1/\tau)。独立选取 (c \tau \log n) 个元素时，所有元素均未选中前 (n/\tau) 位置的概率为： [ \left(1 - \frac{1}{\tau}\right)^{c \tau \log n} \leq e^{-c \log n} = \frac{1}{n^c}. ] 取 (c \geq 1) 即可满足高概率要求。

关键概念总结

• 有效标签：满足边权不等式的顶点距离分配。
• 价格函数：通过调整边权使部分边非负，为Dijkstra算法创造条件。
• 负权顶点：作为负权边起点的顶点，需重点处理。
• 随机采样：通过高概率覆盖关键顶点，限制子问题规模。

3. Fineman与Boilermakers团队的核心工具

3.1 h跳距离与适当负路径

对于图 (G = (V, E))，h跳距离 (d^h(u, v)) 表示从顶点 (u) 到 (v) 使用至多 (h) 条负权边的最短路径长度。该距离可通过 (h) 次Bellman-Ford/Dijkstra迭代计算。

适当h跳距离（proper h-hop distance）由Boilermakers团队[12]提出，定义为恰好使用 (h) 条负权边的最短路径长度。尽管精确计算该距离是NP难的，但通过以下引理可检测是否存在负权路径：

引理3：存在一个 (\tilde{O}(hm)) 时间算法，给定负权顶点集合 (S)，可执行以下操作之一：

1. 找到中和 (S) 的价格函数 (\phi)；
2. 找到一对顶点 ((u, v) \in S)，其存在适当h跳负权路径。

证明思路：通过h次Bellman-Ford/Dijkstra迭代，若某顶点在最后一次迭代中距离减少，则存在恰好h条负权边的负权路径。

弱h跳负三明治（weak h-hop negative sandwich）是一个三元组 ((s, t, N))，其中对任意 (x \in N)，满足： [ d^h(s, x) + d^h(x, t) < 0. ] 通过随机采样负权顶点，Boilermakers团队证明了以下关键结果：

引理4：存在一个 (\tilde{O}(hm)) 时间算法，可执行以下操作之一：

1. 找到弱h跳负三明治 ((s, t, N))，其期望大小 (E(|N|) = hk/a)（(k) 为负权顶点总数，(a) 为采样大小）；
2. 期望中和 (a) 个负权顶点。

参数选择：当 (a = \sqrt{k}) 且 (h = \Theta(1)) 时，算法在 (\tilde{O}(m)) 时间内，要么产生大小为 (\tilde{O}(\sqrt{k})) 的负三明治，要么期望中和 (\sqrt{k}) 个顶点。

3.2 中间性与(τ, β)-图

β-中间性（β-betweenness）定义为顶点对 (u, v) 之间满足 (d^\beta(u, x) + d^\beta(x, v) < 0) 的顶点 (x) 的数量。Fineman[8]通过构造**(τ, β)-图**限制中间性：

(τ, β)-图构造步骤：

1. 随机采样大小为 (c \tau \log n) 的顶点集合 (U)；
2. 构建二分图 (B)，其中 (U) 和 (V) 为顶点集，边权 (w(u, v) = d^\beta(u, v)) 和 (w(v, u) = d^\beta(v, u))。

引理5：给定(τ, β)-图，可在 (\tilde{O}(\tau^2 n)) 时间内找到价格函数 (\phi)，使得所有顶点对的β-中间性至多为 (n/\tau)（高概率）。

证明：

1. 在二分图 (B) 中执行 (2|U|) 次Bellman-Ford/Dijkstra迭代，得到标签 (d(\cdot))；
2. 将 (d(\cdot)) 作为价格函数 (\phi) 应用于原图 (G)；
3. 由于 (U) 中顶点的β跳距非负，任意顶点对的中间性被限制为 (n/\tau)（引理1的高概率覆盖）。

3.3 负三明治的远程化处理

若负权边集合 (N) 在子图 (G(S)) 中的β跳可达顶点数不超过 (m/\tau)，则称 (N) 是**(β, τ)-远程**（remote）的。Boilermakers团队[12]证明，对弱ℓ跳负三明治 ((s, t, N))，若其 (h+\ell)-中间性为 (m/r)，则通过以下价格函数可使其远程化： [ \phi(x) = \min\left(d^{h+\ell}(s, x), -d^{h+\ell}(x, t)\right). ]

引理6：给定弱ℓ跳负三明治 ((s, t, N))，若其 (h+\ell)-中间性为 (m/r)，则可在 (\tilde{O}((\beta+\ell)m)) 时间内使其成为(β, τ)-远程。

技术工具总结

• h跳距离：限制负权边使用次数的最短路径。
• 适当距离：检测恰好h条负权边的路径。
• 负三明治：通过随机采样定位密集负权区域。
• (τ, β)-图：限制顶点对间的中间顶点数量。
• 远程化处理：通过价格函数将负权边限制在局部子图。

4. 包围负权三明治

4.1 (τ_i, β_i)-图序列

对于负权三明治 ((s, t, N))，我们通过递归构建多尺度的**(τ_i, β_i)-图序列**来形成“信封”结构，逐步限制其影响范围。参数设置为： [ \tau_i = \alpha^i \tau_0, \quad \beta_i = \frac{\beta_0}{\alpha^i}, \quad \text{满足} \quad \tau_i \beta_i = \Theta(\sqrt{k}), ] 其中 (\alpha) 是递归因子，(T = O(\log k)) 为递归层数。构建该序列的总时间复杂度为： [ \tilde{O}(\sqrt{k} \cdot m). ]

引理7：
构建(τ_i, β_i)-图序列的时间复杂度为 (\tilde{O}(\sqrt{k} \cdot m))。
证明：
每层构建需 (\tilde{O}(\tau_i \beta_i \cdot m)) 时间，总层数 (T = O(\log k))，且 (\sum_{i=0}^T \tau_i \beta_i = \Theta(\sqrt{k} \cdot \log k))。

4.2 (τ_i, β_i)-信封序列

信封结构（envelope）是通过递归应用价格函数形成的嵌套子图。外层信封 (D_0) 由(τ_0, β_0)-图生成，内层信封 (D_{i+1}) 基于前一层的顶点集合 (A = \cup_{j \leq i+1} U_j \cap D_{j-1}) 构建。

关键性质：

• 每层信封 (D_i) 的大小为 (|D_i| \leq \frac{m}{\tau_i})（高概率）。
• 应用价格函数后，(D_i) 中的顶点对 (s-t) 的β_i-中间性被限制。

引理8：
给定参数 (\tau_i \beta_i = \Theta(\sqrt{k}))，可在期望时间 (\tilde{O}(\alpha \sqrt{k} \cdot m)) 内构建(τ_i, β_i)-信封序列。
证明：
通过引理2的采样性质，顶点集合 (A) 的大小为 (O(\alpha \log n))，每层信封构建的时间复杂度为 (\tilde{O}(|A|^2 \cdot m))，总时间复杂度为 (\tilde{O}(\alpha \sqrt{k} \cdot m))。

关键技术总结

• 递归分层：通过多尺度的(τ_i, β_i)-图逐步缩小负权边的影响范围。
• 信封结构：利用价格函数将负权三明治限制在局部子图中，降低后续计算的复杂度。
• 参数平衡：通过 (\tau_i \beta_i = \Theta(\sqrt{k})) 平衡时间复杂度，确保每层递归的效率。

5. 复杂度分析

5.1 总时间复杂度

算法的总时间复杂度由以下部分构成：

1. 分层图序列构建：(\tilde{O}(\sqrt{n} \cdot m))（引理7）。
2. 负三明治中和：每层递归中和 (\Theta(\sqrt{n})) 个顶点，总时间 (\tilde{O}(\sqrt{n} \cdot m))（引理9）。
3. 远程化处理：每层应用价格函数的时间为 (\tilde{O}(m))，总时间 (\tilde{O}(\sqrt{n} \cdot m))。

定理1：
算法的期望时间复杂度为 (\tilde{O}(m \sqrt{n}))。
证明：
总时间复杂度为分层图构建、中和操作与远程化处理的线性叠加： [ \tilde{O}(\sqrt{n} \cdot m) + \tilde{O}(\sqrt{n} \cdot m) + \tilde{O}(\sqrt{n} \cdot m) = \tilde{O}(m \sqrt{n}). ]

5.2 强多项式性验证

算法的强多项式性依赖以下关键步骤：

1. 价格函数的线性更新：通过降价成本的线性时间更新（(O(m)) per iteration）。
2. 递归分层结构：每层递归的顶点数减少 (\sqrt{n}) 因子，确保总层数为 (O(\log n))。
3. 随机采样的高概率保证：引理1确保采样覆盖关键顶点，避免最坏情况。

6. 结论与未来方向

6.1 研究贡献

本文提出了第一个随机化的(\tilde{O}(m \sqrt{n}))时间Bellman-Ford算法，突破了经典算法的(O(mn))时间复杂度。核心创新包括：

• 递归分层图结构：通过多尺度的((\tau_i, \beta_i))-图将问题分解为更小的子问题。
• 价格函数的线性更新：避免全局距离的重复计算，提升局部优化效率。
• 负权边的远程化处理：将负权边限制在局部子图中，结合Dijkstra和Bellman-Ford迭代高效中和。

6.2 与现有工作的对比

算法	时间复杂度	模型	关键技术
Bellman-Ford (1950s)	(O(mn))	强多项式	逐层松弛
Fineman (2023)	(\tilde{O}(m n^{8/9}))		远程-近邻分层
Boilermakers (2023)	(\tilde{O}(m n^{4/5}))		适当跳距与随机采样
本文	(\tilde{O}(m \sqrt{n}))	强多项式	递归分层与线性价格更新

6.3 未来方向

1. 进一步优化：探索将时间复杂度降低至(\tilde{O}(m \sqrt{n}))以下的可能性，例如通过改进递归因子(\alpha)或分层参数(\tau_i, \beta_i)。
2. 弱多项式结合：研究如何将本文的强多项式框架与弱多项式算法（如(\tilde{O}(m \log C))）结合，以处理边权范围较大的问题。
3. 并行化扩展：分析分层结构在并行计算模型（如MapReduce）中的适用性，探索分布式实现。
4. 应用场景：将算法应用于实际问题，如供应链优化、网络路由等，验证其实用性。

全文总结

本文通过递归分层图结构和价格函数的线性更新，将Bellman-Ford算法的时间复杂度推进至(\sqrt{n})因子，为含负权边的最短路径问题提供了新的理论突破。这一成果不仅完善了算法理论体系，也为实际应用中的优化问题提供了更高效的解决方案。

附录

附录A：算法伪代码

A.1 递归中和负权三明治算法

def neutralize_negative_sandwich(s, t, N, τ, β):
    # 输入：负权三明治(s, t, N)，参数τ, β
    # 输出：中和后的价格函数φ
    if |N| == 0:
        return None
    
    # 步骤1：构建(τ, β)-图
    U = random_sample(V, c * τ * log(n))
    B = build_bipartite_graph(U, V, β)
    
    # 步骤2：计算价格函数φ
    φ = compute_potential(B)
    
    # 步骤3：检测剩余负权边
    remaining_negatives = [e for e in E if w_φ(e) < 0]
    
    if len(remaining_negatives) == 0:
        return φ
    
    # 步骤4：递归处理子问题
    new_N = extract_negative_vertices(remaining_negatives)
    α = sqrt(τ)
    τ_new = τ / α
    β_new = β * α
    φ_sub = neutralize_negative_sandwich(s, t, new_N, τ_new, β_new)
    
    # 步骤5：合并价格函数
    return combine_potentials(φ, φ_sub)

A.2 分层图构建算法

def build_hierarchical_graphs(k):
    # 输入：初始负权顶点数k
    # 输出：分层图序列{(τ_i, β_i)}
    graphs = []
    τ = 1
    β = sqrt(k)
    while τ < k:
        graphs.append( (τ, β) )
        τ *= 2
        β = β / 2
    return graphs

附录A1：关键引理的详细证明

A1.1 引理1（随机采样覆盖性）

引理：随机选取大小为 (c \tau \log n) 的子集 (S)，则前 (n/\tau) 个元素中至少有一个被选中的概率 (\geq 1 - 1/n)。
证明：
每个元素不在前 (n/\tau) 位置的概率为 (1 - 1/\tau)。独立选取 (c \tau \log n) 个元素时，所有元素均未选中前 (n/\tau) 位置的概率为： [ \left(1 - \frac{1}{\tau}\right)^{c \tau \log n} \leq e^{-c \log n} = \frac{1}{n^c}. ] 取 (c \geq 1)，则失败概率 (\leq 1/n)。

A1.2 引理7（分层图构建复杂度）

引理：构建(τ_i, β_i)-图序列的时间复杂度为 (\tilde{O}(\sqrt{k} \cdot m))。
证明：
每层构建需 (\tilde{O}(\tau_i \beta_i \cdot m)) 时间。由于 (\tau_i \beta_i = \Theta(\sqrt{k}))，总层数 (T = O(\log k))，总时间为： [ \sum_{i=0}^T \tilde{O}(\sqrt{k} \cdot m) = \tilde{O}(\sqrt{k} \cdot m \cdot \log k) = \tilde{O}(\sqrt{k} \cdot m). ]

附录说明

• 伪代码注释：
  1. random_sample 函数通过蓄水池采样实现，确保高概率覆盖关键顶点。
  2. compute_potential 使用Bellman-Ford/Dijkstra迭代计算价格函数。
• 证明补充：
  引理1的高概率覆盖性是分层图构建的基础，确保递归过程中顶点数量指数级减少。