正权有向图上次短路径问题更快的算法

· · 算法·理论

这篇论文只能做到 \widetilde O(n^4m^3) 的时间复杂度？玩的太差了。这题可以做到 \widetilde O(n^2m^3) 的时间复杂度。 在 m=\Theta(n) 的稀疏图上，从七次方降到五次方。核心不是加速某一次最短路，而是：

把“消去非最短路核心顶点”和“细分边”都移到正确性证明中；实际算法始终在原图上做最短路，并且只枚举原始边，不枚举细分位置。

下述是我基于 Chen–Wein–Zhang 核心引理得到的改写，不是原文已经声明的复杂度；我给出完整的归约与正确性论证，但仍需要独立复核。

我核对了其 2026 年 7 月 13 日的 v2：主定理仍是严格正实数边权下的 O(n^4m^3\log n)。作者也明确提到，避免边细分可能得到 O(n^4m^2\log n)。下面不止省掉细分操作，还要避免在消元产生的稠密图上运行最短路。(arXiv)

一、先提取最短路核心，并处理一类容易的答案

设

d(v)=\operatorname{dist}_G(s,v),\qquad \bar d(v)=\operatorname{dist}_G(v,t),\qquad D=d(t).

若 D=\infty，直接报告无解。以下考虑 s\ne t，且边权严格为正。

定义最短路核心

S=\{v:d(v)+\bar d(v)=D\},

以及核心上的紧边图

H=(S,F),\qquad F=\{(u,v)\in E:\ u,v\in S,\ d(u)+w(u,v)=d(v)\}.

记

q=|S|,\qquad p=|F|.

因为边权严格为正，H 中每条边都严格增加 d，所以 H 是 DAG。每个核心顶点都有完全位于 H 中的最短前缀与最短后缀。

1. 非下降的非紧连接可以直接处理

考虑一段 x\to y 路径 R，其中 x,y\in S、x\ne y，且所有内部顶点都在 V\setminus S。也允许 R 就是一条原图边。

假设

d(x)\le d(y),\qquad w(R)>d(y)-d(x).

取任意核心最短路 P_{sx} 与 P_{yt}，则

P_{sx}\circ R\circ P_{yt}

是一条简单路：前缀上的顶点高度至多 d(x)，后缀上的顶点高度至少 d(y)，两者不交；中段内部不在核心，也不会与它们相交。高度相等时，由 x\ne y 及核心路径上的严格单调性，结论仍然成立。

其长度为

d(x)+w(R)+D-d(y)>D. \tag{1}

如果某条最优严格次短路包含这样的中段，我们就能直接找到不比它更长的合法答案。因为该最优路的前缀、后缀分别不会比 d(x)、D-d(y) 更短。

2. 怎样找这些连接，不额外增加指数？

分开处理两种情况：

第二种 Dijkstra 中，其他核心顶点只允许到达、不允许继续扩展；并且禁止从 x 直接进入另一核心顶点，因为直接边已单独处理。

这里有一个细节：不能把紧边和外部绕行一起只保留最短者，否则一条紧边可能掩盖我们需要检查的更长绕行。

外部绕行一定是非紧的：否则把它接上两端最短路，就得到经过非核心顶点的最短 s-t 路，与核心的定义矛盾。

这一部分总计

O\bigl(q(m+n\log n)\bigr).

算法最终会对容易部分和后面的困难部分统一取最小值。下面只是在证明上把尚需处理的情况归结为：

最优解中，相邻两次访问核心之间的每一段非紧连接，都从较大的 d 下降到较小的 d。

二、困难部分：只枚举两个端点和两条原始紧边

枚举

A,B\in S,\qquad d(A)>d(B),

以及两条原始紧边

e=(x_0,x_1),\qquad f=(y_0,y_1)\in F.

只保留高度开区间重叠的边对：

\boxed{ \max\{d(x_0),d(y_0)\} < \min\{d(x_1),d(y_1)\}. } \tag{2}

可以把这理解为：两条边都跨过了某个共同的水平切面。但我们不枚举这个切面的位置。

1. 寻找两条受指定边约束的不交外侧路径

我们需要在 H 中找

P_1:s\to A,\qquad P_2:B\to t,

使得 P_1 经过 e，P_2 经过 f，且二者顶点不交。

这只需两次 DAG 双路径查询：

\begin{aligned} &\text{下半部分：} &&s\to x_0,\quad B\to y_0;\\ &\text{上半部分：} &&x_1\to A,\quad y_1\to t. \end{aligned} \tag{3}

每一行内部要求两条路径顶点不交。

为什么两行可以独立求解？由式 (2)，存在一个高度 c，满足

d(x_0),d(y_0)<c<d(x_1),d(y_1).

下半部分的所有顶点都在 c 以下，上半部分都在 c 以上。因此分别找到不交路径后，再接上 e,f，就得到完整的不交路径对。

DAG 上指定两对端点的顶点不交路径可在线性时间求出；这是 Tholey 的结果，也是 CWZ 使用的子程序。于是这一过程耗时 O(q+p)。(科学直通车)

2. 删除外侧路径顶点，在原图上找中段

令

Z=\bigl(V(P_1)\cup V(P_2)\bigr)\setminus\{A,B\}.

在原图 G-Z 中，用 Dijkstra 求最短 A\to B 路 R。

若存在，则

P=P_1\circ R\circ P_2

是合法候选。

这里删除的是顶点，不是边。因此三部分除连接端点外互不相交，拼接结果一定简单。同时，

\begin{aligned} w(P) &=d(A)+w(R)+D-d(B)\\ &=D+\bigl(d(A)-d(B)\bigr)+w(R)\\ &>D. \end{aligned} \tag{4}

注意，中段 R 不需要额外满足“第一条边后退”“最后一条边后退”等约束。只要 d(A)>d(B)，严格非最短性就已经有保证。

到这里，算法非常直接：

枚举 (A,B,e,f)，找任意一对满足条件的不交外侧路径，删除它们的顶点，在原图求中段最短路，更新答案。

每个产生的候选都合法。真正需要证明的是：至少有一组枚举能够保住最优答案。

三、正确性：两次图变换只出现在证明中

这是改进里最关键的部分。

3.1 定义一个不实际构造的捷径图 K

图 K 的顶点集是 S。

它保留全部紧边 F。此外，对于每对满足 d(x)>d(y) 的核心顶点，定义

c_{xy} = \min\left\{ w(R): R\text{ 是 }x\to y\text{ 路径，且内部顶点不在 }S \right\}.

这里允许 R 是直接边。若 c_{xy}<\infty，就在 K 中放一条权重为 c_{xy} 的 x\to y 边。

因此 K 只有两类边：

\text{原始紧边，或者严格降低 }d\text{ 的捷径。}

算法不计算这些捷径，也不构造 K。

所有 K 中的边都满足

w_K(x,y)\ge d(y)-d(x),

而原来的核心最短路仍然存在，所以

\operatorname{dist}_K(s,v)=d(v),\qquad \operatorname{dist}_K(v,t)=D-d(v).

于是 K 的每个顶点仍然处于某条最短 s-t 路上。

现在取原图的一条最优严格次短路 P^*。如果第一部分没有保住它，那么它的每段非紧核心间连接都是下降的。把这些连接分别换成 K 中相应的最便宜捷径，得到：

故有

\boxed{\operatorname{OPT}_K\le \operatorname{OPT}_G.} \tag{5}

此时还不能直接声称 K 中的简单路能展开成原图简单路。不同捷径可能经过同一个非核心顶点。这个风险要留到最后单独解决。

3.2 在证明中细分紧边，调用 CWZ 核心引理

仅在证明中，把 K 的每条紧边按照核心顶点的不同 d 值细分，使每条前进边只跨一个层间隙；下降边不变。记所得分层图为 L。

新增虚拟顶点只有一条入边、一条出边，因此细分前后的完整简单路径保持一一对应，长度不变。

对 L 中的一条最优严格次短路，设中段从第一条后退边的起点 A，延伸到最后一条后退边的终点 B。CWZ 的 Lemma 5.4 保证

d(A)>d(B).

由于下降边没有被细分，A,B 都是原来的核心顶点。(arXiv)

其 Lemma 5.5 进一步保证，存在两条跨同一层间隙的前进边，使至少一对满足指定过边条件的不交外侧路径存在；并且任意一对满足条件的外侧路径，都避开该最优中段的内部顶点。(arXiv)

我们只调用这个引理，不修改它的证明。

3.3 为什么可以合并所有细分位置？

设引理选中的两条细分边，分别来自原始紧边 e,f。

它们跨越同一层间隙，所以原始 e,f 的高度区间必然满足式 (2)。

关键是：

对端点位于 S 的前进路径，“经过原边 e 的某条细分子边”等价于“经过整条原边 e”。

原因很简单：细分产生的内部顶点没有其他进出口。

因此，不管引理选中原边 e 的哪一个细分位置，约束的都是同一个原始路径集合。对 f 也一样。

这意味着，我们枚举原始 (A,B,e,f) 后选出的任意合法外侧路径对，细分后都满足引理选定的过边约束，从而避开最优中段。

所以：

\boxed{ \text{只需枚举原始边对，不必再枚举层或细分位置。} }

这里省掉了一个层数因子。

3.4 捷径展开可能重复顶点，但原图 Dijkstra 可以修复

设 K 的最优中段为

R_K^*:A\to B.

由上述隔离性质，算法选出的 P_1,P_2 避开它的所有内部核心顶点。

把 R_K^* 中的捷径展开为原图路径，得到一个 A\to B walk，记为 W。它可能重复非核心顶点，但有两个重要性质：

第一，外侧路径完全位于核心 S，而每条捷径的内部顶点都位于 V\setminus S。

第二，中段的内部核心顶点已经由隔离引理保证不在外侧路径上。

因此，整个展开后的 W 都存在于

G-Z

之中，而且

w(W)=w(R_K^*).

原图 Dijkstra 找到的最短 A\to B 路 R 于是满足

w(R)\le w(W)=w(R_K^*).

严格正权保证 R 简单。即便去掉了展开过程中产生的回路，也不会意外变成最短 s-t 路，因为式 (4) 中的 d(A)>d(B) 始终不变。

最终，

\begin{aligned} w(P_1\circ R\circ P_2) &\le d(A)+w(R_K^*)+D-d(B)\\ &=\operatorname{OPT}_K\\ &\le\operatorname{OPT}_G. \end{aligned} \tag{6}

左边又是一条原图中的合法严格非最短简单路，所以不可能小于 \operatorname{OPT}_G。因此所有不等式都取等号，算法找到了最优答案。

这就完成了正确性证明。

尤其值得强调：我们并不需要证明“所有捷径都能无冲突展开”。我们只需要证明，在已经固定并删除外侧路径后，最优中段能够展开成一个残图中的 walk。剩下的简单性由原图最短路负责。

四、复杂度：枚举 q^2p^2 组，每组在原图上工作

候选参数数量至多为

q^2p^2.

每组参数的工作量为

O(q+p)+O(m+n\log n).

再加上容易部分，总时间为

O\!\left( (q+q^2p^2)(m+n\log n) \right). \tag{7}

先删除从 s 不可达或无法到达 t 的顶点后，有 m\ge n-1。结合 q\le n,\ p\le m，得到

\boxed{ O(n^2m^3\log n) = \widetilde O(n^2m^3). }

对比如下。前两行分别是论文正式给出的界，以及作者注明的可能改进方向；第三行是上述推导。(arXiv)

方案 一般图 m=\Theta(n) m=\Theta(n^2)
CWZ 原定理 \widetilde O(n^4m^3) \widetilde O(n^7) \widetilde O(n^{10})
作者提到的免细分方向 \widetilde O(n^4m^2) \widetilde O(n^6) \widetilde O(n^8)
本次改写 \widetilde O(n^2m^3) \widetilde O(n^5) \widetilde O(n^8)

这里的两个实质变化是：合并同一原始边对对应的所有层位置；并且证明残图最短路可以直接在原图运行，不承受捷径稠密化和细分的规模膨胀。

时间界按精确加法、比较的算术模型计；有理数输入的位复杂度需要另计。

实现中也不必依赖难写的线性双路径算法

我写的参考实现使用了一个更朴素、但经过批量预处理的 DAG 动态规划。

固定两个源点，记录每对终点是否存在顶点不交的两条路径。在转移时，回退拓扑序较大的终点，可以在 O(qp+q^2) 时间内求出全部终点对并保存路径前驱。

对所有 B 预处理源对 (s,B)，再在反图上对所有 A 预处理源对 (t,A)，总预处理为

O(q^2p),

空间为 O(q^3)。之后恢复一对路径只需 O(q) 时间。因此参考代码同样没有在每组枚举中额外乘上一个 q。

五、一个多后退边的例子，以及实际验证

例如取六个顶点 0,\ldots,5，高度

d=(0,2,4,5,7,8).

紧边为

01,\ 12,\ 23,\ 34,\ 45,\ 04,\ 13,\ 25,

每条紧边权重取两端高度差。另加两条后退边：

4\to3\text{，权重 }3;\qquad 3\to1\text{，权重 }4.

最短路长度为 8，严格次短路为

0\to4\to3\to1\to2\to5,

长度

7+3+4+2+4=20.

这里中段是

4\to3\to1,

含两条后退边；外侧路径是 0\to4 与 1\to2\to5。因此本算法并没有把问题错误地简化为“最短路加一条非紧边”。

参考实现已经与“枚举该图所有简单 s-t 路，再取第二个不同长度”的穷举答案对拍了 14,546 个实例，包括全部 4,096 个四顶点无自环无权有向图，以及正整数权、正有理数权、大量并列最短路、核心外绕行和多后退边实例，未发现不一致。有限测试只用于检查实现，不替代上面的证明。

当前能够完整落实的改进是：稀疏图七次方降到五次方，而且仍然求最优的严格非最短简单路，不只是判断其存在。

再向下优化，具体瓶颈已经变成了这 q^2p^2 组不同删点集下的最短路查询。不能直接用一次 APSP 替代，因为被删除的两条外侧路径随 (A,B,e,f) 改变。进一步降低指数，需要压缩这些外侧路径的选择，或者找到能批量处理这些特殊删点集的结构；上述五次方界则不需要再假设这样的新结构。

TCS 论文就是简单。