D‘Esopo-Pape 算法：基于双端队列的含负边单源最短路径解法（cp-algorithms 实现与测试全解析）

• 文档
• 教程
• 知识库

本篇文章以 cp-algorithms 仓库中的 src/graph/desopo_pape.md 为主体，系统讲解 D'Esopo-Pape（也称 Levit）算法：它面向带负权边、但无负环的图，用三集合状态划分配合双端队列（deque）完成单源最短路径求解，在多数场景下比 Dijkstra 算法 与 Bellman-Ford 算法 更快。读完本文，你将掌握该算法的三集合标记语义、完整可运行的 C++ 实现、前驱数组的路径还原方法，以及它的最坏情形复杂度陷阱，并看到仓库测试用例如何对含负边图进行正确性验证。

1. 问题定义与适用边界

给定一个包含 $n$ 个顶点、$m$ 条边（权重为 $w_i$）的图，以及一个起始顶点 $v_0$，任务是求出从 $v_0$ 到每一个其他顶点的最短路径长度。

D'Esopo-Pape 算法在大多数情况下会比 Dijkstra 算法 和 Bellman-Ford 算法 运行得更快，并且支持负权边。

但需要注意其适用边界：

• 允许负权边：算法不要求边权非负，因此比只能处理非负边权的 Dijkstra 适用面更广；
• 不允许负权环：若图中存在负权环，最短路径将无定义（长度趋于 $-\infty$），算法无法正确收敛；
• 这一“能处理负边、不能处理负环”的定位与 Bellman-Ford 算法 的适用场景一致，区别在于 Pape 用队列驱动松弛，平均性能更好。

2. 核心思想：三集合状态划分与松弛规则

算法维护两个数组：

• $d$：当前最短路径长度数组，$d_i$ 表示从 $v_0$ 到顶点 $i$ 的当前最短距离。初始时除 $d_{v_0} = 0$ 外，其余全部为 $\infty$；算法结束后 $d$ 即最终答案；
• $p$：当前前驱（祖先）数组，$p_i$ 表示从 $v_0$ 到 $i$ 的当前最短路径上 $i$ 的直接前驱。$p$ 与 $d$ 同步逐步更新，最终形成完整的最短路径树。

算法在每一步维护三个顶点集合：

集合 $M_1$ 中的顶点存放在一个**双向队列（deque）**中。算法每步执行如下操作：

1. 从队列前端取出一个顶点 $u$（即当前 $M_1$ 的队首）；
2. 将 $u$ 移入集合 $M_0$；
3. 遍历从 $u$ 出发的所有边 $(u, v)$，权重为 $w$，按 $v$ 当前所属集合分三种情况处理：

• 若 $v \in M_2$：将 $v$插入队列末尾（加入 $M_1$），并置 $d_v = d_u + w$；
• 若 $v \in M_1$：尝试改进 $d_v = \min(d_v, d_u + w)$。由于 $v$ 已在 $M_1$ 中，无需再入队；
• 若 $v \in M_0$：若 $d_v$ 可被改进（即 $d_v > d_u + w$），则更新 $d_v$，并把 $v$放回队列开头（重新标记为 $M_1$），以便尽快重新松弛。

每次更新 $d$ 数组时，必须同步更新对应的 $p$ 数组元素（前驱），这与 Dijkstra 算法的路径还原思想 一致。

关键设计在于：从队首取出、处理完的顶点一旦后续被更短路径再次改进，会立即插回队首，从而让“被反超”的顶点优先被重新处理。这是该算法区别于 SPFA 等纯 FIFO 队列变体的核心机制，也是它平均表现优异的原因。

3. 完整 C++ 实现与逐段解读

仓库文档 src/graph/desopo_pape.md 给出了完整实现。为便于对照，此处保留原代码并用注释标注关键状态转换（m数组即顶点所属集合的标记：2对应 $M_2$、1对应 $M_1$、0对应 $M_0$）：

struct Edge { int to, w; }; int n; vector<vector<Edge>> adj; const int INF = 1e9; void shortest_paths(int v0, vector<int>& d, vector<int>& p) { d.assign(n, INF); d[v0] = 0; vector<int> m(n, 2); // 初始：所有顶点都在集合 M2（尚未计算） deque<int> q; q.push_back(v0); // 起点入队并成为 M1 的一员 p.assign(n, -1); while (!q.empty()) { int u = q.front(); q.pop_front(); m[u] = 0; // u 移入集合 M0（距离已计算，但可能被后续改进） for (Edge e : adj[u]) { if (d[e.to] > d[u] + e.w) { // 尝试松弛 d[e.to] = d[u] + e.w; p[e.to] = u; // 同步更新前驱 if (m[e.to] == 2) { // M2 -> M1：插到队尾 m[e.to] = 1; q.push_back(e.to); } else if (m[e.to] == 0) {// M0 被改进：重新入 M1，插到队首 m[e.to] = 1; q.push_front(e.to); } // 若 m[e.to] == 1（已在 M1 中），仅更新 d 与 p，不再入队 } } } }

实现要点：

• 邻接表表示：adj[u]存放从 $u$ 出发的所有边（目标顶点to与权重w），图既可有向也可无向；
• INF 取值：代码中INF = 1e9，应保证大于任何可能的路径长度。若边权可为负，需注意类似 Bellman-Ford 中“从无穷大再松弛”的隐患——不过本算法只在顶点首次入队（$M_2 \to M_1$）时用精确的 $d_u + w$ 直接赋值，$M_1$、$M_0$ 分支都要求满足d[e.to] > d[u] + e.w才更新，天然避免了 $\infty - 1$ 这类错误距离的产生（可对比 bellman_ford.md 中的相关说明）；
• 标记数组m：一个int数组即可承载三集合语义，避免了维护三个独立容器的开销；
• 队尾入队 / 队首入队：新发现的顶点走push_back，被改进的旧顶点走push_front，前者遵循广度式扩散，后者体现“反超者优先重处理”的优先级。

4. 仓库中的验证：负边测试用例与自动化构建

仓库为本文档提供了可直接运行的单元测试 test/test_desopo_pape.cpp。其构造的图包含负权边：

• 顶点 $0 \to 1$ 权重 $-1$（负边）
• 顶点 $0 \to 2$ 权重 $4$
• 顶点 $1 \to 2$、$1 \to 3$、$1 \to 4$ 权重分别为 $3$、$2$、$2$
• 顶点 $3 \to 2$ 权重 $5$、$3 \to 1$ 权重 $1$
• 顶点 $4 \to 3$ 权重 $-3$（负边）

调用shortest_paths(0, d, p)后，测试断言：

vector<int> d_ideal{0, -1, 2, -2, 1}; vector<int> p_ideal{-1, 0, 1, 4, 1};

其中d的期望值体现了负边松弛的链式改进：$d_4 = 1$（经 $0 \to 1 \to 4$）后，又通过 $4 \to 3$（$-3$）将 $d_3$ 压到 $-2$，前驱记为 $4$。这说明算法对负边带来的“后到先得”式改进能够正确收敛，且p数组同步维护无误。

关于测试的运行方式，仓库在 test/extract_snippets.py 中通过正则^\s*```\{.cpp\s+file=(\S+)\}$从src/目录下所有.md文档中抽取命名代码块（例如desopo_pape），生成对应的.h头文件供测试源码#include；随后 test/test.sh 用g++ -std=c++17逐个编译运行所有*.cpp测试并断言退出码。也就是说，本文第 3 节展示的实现片段与测试断言之间形成了“文档代码即被测代码”的闭环，任何对算法实现的改动都会在仓库 CI 中得到校验。读者可参考 CONTRIBUTING.md 了解测试的维护约定。

5. 复杂度分析与最坏情形警示

关于复杂度，原文档给出的是经验性结论：

• 平均/多数场景：算法通常表现相当快，多数情况下甚至快于 Dijkstra 算法，这是因为队列机制避免了 Dijkstra 在稠密图上重复扫描最小值的开销，也避免了 Bellman-Ford 算法 固定 $n-1$ 轮全边扫描的低效；
• 最坏情形：存在精心构造的图，使该算法退化到指数级时间，因此它不适合在需要最坏情形时间保证的场景中使用。Stack Overflow 与 Codeforces 上对此有公开讨论（可在原文档第 90–92 行的链接中找到），结论一致：Pape 的算法不是多项式时间算法。

由此给出的工程建议：

6. 路径还原与相关算法导航

6.1 利用 $p$ 数组还原最短路径

算法结束后，对任意目标顶点 $t$，可沿前驱链从 $t$ 回溯至 $v_0$。仓库中 dijkstra.md 的restore_path实现 展示了通用做法：

vector<int> restore_path(int s, int t, vector<int> const& p) { vector<int> path; for (int v = t; v != s; v = p[v]) path.push_back(v); path.push_back(s); reverse(path.begin(), path.end()); return path; }

该片段同样适用于本算法的p数组（前驱以 $-1$ 表示不存在）。

6.2 在仓库中的位置与延伸阅读

本文档位于仓库图形算法模块的“单源最短路径”系列中，参见 src/navigation.md（导航中紧随 Dijkstra、稀疏图 Dijkstra 与 Bellman-Ford 之后）。建议按如下路径系统学习：

1. 先掌握 Dijkstra 算法（非负边权基准解）及其 稀疏图优化；
2. 再读 Bellman-Ford 算法，理解负边与负环的处理框架；
3. 最后回到本文的 D'Esopo-Pape，体会“三集合 + 双端队列”在负边场景下对前两者的加速思想；
4. 用 test/test_desopo_pape.cpp 的负边用例亲手跑一遍（见第 4 节的构建方式），验证算法行为。

结语

D'Esopo-Pape 算法在“允许负边、禁止负环”的问题域内，用一套优雅的三集合状态机与双端队列调度，提供了平均意义上极快的单源最短路径求解。它最大的价值在于用极简的数据结构换来了对 Dijkstra 的普遍反超，代价是缺少最坏情形的多项式上界——这正是竞赛与工程实践中需要权衡的核心点。结合本仓库的完整实现、负边测试用例与自动化抽取构建机制，读者可以放心地在自己的项目中复现、测试并扩展这一算法。

• 文档
• 教程
• 知识库