OI-wiki 图论专题第 k 短路问题——A* 搜索与可持久化可并堆解法全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文基于 OI-wiki 图论章节的 kth-path 文档 编写系统讲解有向图中第 k 短路径更准确地说是第 k 短途径k-shortest walk问题的两类主流解法基于 A* 搜索的朴素做法以及基于最短路树与可持久化可并堆的 $O(m\log m k\log k)$ 高效做法。读完本文你将掌握两种算法的完整推导脉络、复杂度分析与可直接套用的 C 参考实现并能独立完成 Library Checker - K-Shortest Walk 与「SDOI2010」魔法猪学院等经典题目。问题描述给定一个有 $n$ 个结点、$m$ 条边的有向图求从起点 $s$ 到终点 $t$ 的所有不同路径中的第 $k$ 短路径的长度。「路径」的严格定义需要特别澄清一个术语细节本文所说的「路径」允许经过同一条边或同一个结点多次因此严格的名称应当是「途径walk」而非「路径path」。也就是说本文讨论的问题严格地说是第 k 短途径k-shortest walk问题关于「途径」与「路径」的严格区分可参见图论基础概念。依据 OI 界的习惯本文仍沿用「路径」这一名称若讨论不自交的路径则会明确称之为「简单路径」。这一区分并非咬文嚼字它直接决定了算法的形态因为允许重复经过结点与边A* 搜索和基于偏离边sidetrack的枚举才能在理论上自洽——在简单路径定义下枚举所有偏离边序列并不总是对应合法路径。方法一A* 搜索求解 k 短路算法思想A* 算法是一种最佳优先搜索算法它为每个当前状态 $x$ 设置估价函数$$ f(x) g(x) h(x), $$其中 $g(x)$ 是从初始状态到达当前状态的实际代价$h(x)$ 是从当前状态到达目标状态的最佳路径的估计代价。搜索时每次取出 $f(x)$ 最优的状态 $x$扩展其所有后继状态用优先队列维护这个值。A* 算法在搜索基础一节中有更完整的阐述。在求解 k 短路时将 $h(x)$ 取为从当前结点到达终点 $t$ 的最短路径长度——这个值是无懈可击的最优估计可以通过在反向图上从 $t$ 出发跑一次单源最短路Dijkstra预处理出来记为 $h(x) d_t(x)$。对于每个状态需要记录两个值当前到达的结点 $x$ 和已经走过的距离 $g(x)$将状态记为 $(x, g(x))$。算法流程如下初始化将状态 $(s, 0)$ 加入优先队列每次取出估价函数 $f(x) g(x) h(x)$ 最小的状态枚举该状态所在结点 $x$ 的所有出边将对应的后继状态 $(v, g(x)w)$ 加入优先队列当某个结点第 $k$ 次被从优先队列中取出时对应状态的 $g(x)$ 就是从 $s$ 到该结点的第 $k$ 短路的长度。剪枝优化上述搜索过程还可以进一步优化。由于我们只需要从 $s$ 到 $t$ 的第 $k$ 短路因此当一个结点被取出的次数大于 $k$ 次时就不再扩展它的后继状态。理由如下之前 $k$ 次取出该结点时已经形成了到达该结点的 $k$ 条合法路径足以用来构造到达目标结点的前 $k$ 条最短路继续扩展它不会影响最终答案。复杂度分析若使用优先队列优化 Dijkstra 算法由于至多会将所有边加入优先队列 $k$ 次算法的时间复杂度为 $O(km\log km)$空间复杂度为 $O(km)$。相较于直接搜索如朴素 BFS 式枚举A* 算法针对目标结点 $t$ 进行了剪枝但需要强调这仅仅改良了常数并没有改变渐近复杂度。不过该算法有一个独特的优点——它可以在相同的复杂度内求出从起点 $s$ 到以 $t$ 为根的最短路树中每个结点的前 $k$ 短路而不仅仅是到 $t$ 的。参考实现仓库中提供了对应 Library Checker - K-Shortest Walk#include iostream #include queue #include vector constexpr long long inf 0x3f3f3f3f3f3f3f3f; struct Edge { int u, v, c; Edge(int u, int v, int c) : u(u), v(v), c(c) {} }; int n, m, s, t, k; std::vectorstd::vectorint gr, ig; // 原图与反向图 std::vectorEdge edges; // 边表 std::priority_queuestd::pairlong long, int, std::vectorstd::pairlong long, int, std::greater pq; std::vectorlong long dist_t; // 在反向图上从 t 出发跑 Dijkstra求出每个结点到 t 的最短距离 void calc_distances_to_t() { dist_t.assign(n, inf); dist_t[t] 0; pq.emplace(dist_t[t], t); while (!pq.empty()) { long long di pq.top().first; int cur pq.top().second; pq.pop(); if (di dist_t[cur]) continue; for (auto e : ig[cur]) { int nxt edges[e].u; auto di_nxt di edges[e].c; if (di_nxt dist_t[nxt]) { dist_t[nxt] di_nxt; pq.emplace(di_nxt, nxt); } } } } std::vectorlong long ans; // A* 搜索求解 k 短路复杂度 O(k * m * log(k * m)) void find_k_shortest_walks() { ans.assign(k, -1); std::vectorint cnt(n); pq.emplace(dist_t[s], s); while (!pq.empty()) { long long cost pq.top().first; int cur pq.top().second; pq.pop(); if (cost inf) continue; // 跳过不可达结点 if (cur t) ans[cnt[t]] cost; cnt[cur]; if (cnt[t] k) break; // 终点被取出 k 次终止 if (cnt[cur] k) continue; // 同一结点至多扩展 k 次 for (auto e : gr[cur]) { int nxt edges[e].v; // 估价 当前实际代价 - 当前点h 边权 后继点h auto cost_nxt cost - dist_t[cur] edges[e].c dist_t[nxt]; pq.emplace(cost_nxt, nxt); } } } int main() { std::cin n m s t k; gr.resize(n); ig.resize(n); edges.reserve(m); for (int i 0; i m; i) { int u, v, c; std::cin u v c; edges.emplace_back(u, v, c); gr[u].push_back(i); ig[v].push_back(i); } calc_distances_to_t(); find_k_shortest_walks(); for (auto x : ans) std::cout x \n; return 0; }实现要点优先队列中的键值cost - dist_t[cur] edges[e].c dist_t[nxt]就是后继状态的估价 $f g h$其中 $g cost - dist_t[cur] edges[e].c$ 是到达后继结点的新实际代价$dist_t[nxt]$ 是其 $h$ 值cnt[cur] k的剪枝与cnt[t] k的提前终止对应前文所述的优化若某个结点到 $t$ 不可达其dist_t为inf这些状态在弹出时会被直接跳过。方法二可持久化可并堆——$O(m\log m k\log k)$ 的高效解法前述 A* 算法事实上求出了到达所有结点的 k 短路。如果仅仅想要得到到达指定目标结点$t$ 的 k 短路可以做得更快。本节介绍一种基于可持久化可并堆的 $O(m\log m k\log k)$ 做法其思想源于 Eppstein 算法的简化版本也是可持久化可并堆这一数据结构的典型应用场景。动机不同路径之间可能相差不大A* 算法的瓶颈在于只有到达目标结点 $t$ 时才会更新答案。但不同路径之间往往相差并不大——例如次短路区别于最短路可能仅仅是在一条边处多绕了一个结点而路径的其他部分完全相同。A* 却可能需要重复搜索一遍这些相同的边才能找到次短路。因此如果能把「绕路的部分」单独提取出来只需考虑代价最小的 $k$ 种绕路方式就能高效构造出前 $k$ 条最短路。这引出了最短路树与偏离边的概念。最短路树Shortest Path Tree在反向图上从目标结点 $t$ 出发跑单源最短路记录每个结点 $x$ 到 $t$ 的最短路长度 $h(x)$并记录从结点 $x$ 开始的最短路经过的第一条边$f_x$若存在多个最优选择任取其一即可。所有这些边 $f_x$ 及其端点构成一棵树且树上的每个结点 $x$ 到根节点 $t$ 的简单路径都是 $x$ 到 $t$ 的一条最短路径。这棵树就是最短路树$T$。偏离边Sidetrack与偏离成本求得最短路树 $T$ 后就可以计算每条不在 $T$ 上的边会多绕多少路。对于边 $e(u,v)\notin T$边权为 $w$定义一条新的边仍然从 $u$ 指向 $v$但代价为$$ \Delta(e) w h(v) - h(u). $$本文称这些权值为 $\Delta(e)$ 的边为偏离边sidetrack权值 $\Delta(e)$ 为偏离成本。其含义直观而深刻若当前已沿最短路走到 $u$本可直接沿树边以 $h(u)$ 的代价到达 $t$改走这条非树边 $(u,v)$ 后到达 $t$ 的代价变为 $w h(v)$两者之差恰为 $\Delta(e)$——即这条边带来的额外开销。注意如果一条边的端点并非全部在最短路树 $T$ 里它就不会影响到达结点 $t$ 的 k 短路计算可以将其直接删掉实现中对应dist_t[edge.u] inf dist_t[edge.v] inf的过滤条件。下图左侧是有向图 $G$右侧是对应的最短路树 $T$粗边和相应的偏离边细边关键性质原图路径与偏离边序列一一对应设一条从 $s$ 到 $t$ 的路径经过的边集为 $P$去掉 $P$ 中与 $T$ 的交集得到 $P$。将 $P$ 中的边顺次排列相邻的两条边 $e_1(u_1,v_1)$ 和 $e_2(u_2,v_2)$ 一定满足条件 $(*)$后者的起点 $u_2$ 是前者的终点 $v_1$ 在最短路树 $T$ 上的祖先包括其自身。这是因为在对应的原始路径 $P$ 中$v_1$ 和 $u_2$ 之间连接了若干条 $T$ 中的树边。反过来对于一个满足条件 $(*)$ 的偏离边集 $P$一定存在唯一一条图 $G$ 中的路径 $P$ 与之对应——因为 $v_1$ 和 $u_2$ 在最短路树 $T$ 上的简单路径是唯一的。由此得到本解法的核心等价关系原图中的任意路径 $P$ 与满足条件 $(*)$ 的偏离边序列 $P$ 一一对应且路径 $P$ 的长度等于最短路长度 $h(s)$ 与所有偏离成本之和$$ \operatorname{len}(P) h(s) \sum_{e\in P}\Delta(e). $$于是寻找 k 短路的问题转化为寻找成本第 $k$ 小且满足条件 $(*)$ 的偏离边序列 $P$。图变换把祖先条件变成「首尾相接」为处理条件 $(*)$与其每次查询时在最短路树上寻找祖先不如直接将每个结点的偏离边集合下传到最短路树上的子孙结点。这相当于构造一个新图 $G$在 $G$ 中条件 $(*)$ 就转化为要求 $P$ 中的边首尾相接也就是说 $P$ 是图 $G$ 中的一条路径。问题进一步转化为在图 $G$ 中寻找从 $s$ 出发的、长度第 $k$ 小的到达任意结点的路径。相对于原始的 k 短路问题此处不再要求路径必须结束在目标结点 $t$。转化后的问题变得非常简单直接从起始结点 $s$ 出发求单源最短路每次从优先队列中取出一个结点就相当于找到了一条图 $G$ 中的路径也就对应着图 $G$ 中一条到达目标结点 $t$ 的路径。可持久化可并堆优化算法思路已经清晰但朴素实现的复杂度过高由于图 $G$ 中单个结点处的边规模可能是 $\Theta(m)$ 的每次求单源最短路时都可能需要将规模为 $\Theta(m)$ 的边集压入优先队列。实际上没有必要这么做压入队列的这些边只有最短的那些才可能在后续计算中被弹出。也就是说完全可以将单个结点处的整个边集作为一个存储单元压入优先队列每次只需能够快速访问边集中的最短边即可。这启发我们使用小根堆来存储单个结点处的边集在求单源最短路的优先队列中只存储这些堆其成本就是堆顶元素对应的最短路成本每次弹出队首时需要从队首的堆中弹出堆顶边然后既要将弹出堆顶后的堆压回优先队列也要将堆顶边终点处的偏离边集合对应的堆顶压入优先队列。使用堆存储边集还顺带解决了「沿最短路树下传边集」的问题下传边集相当于把当前结点的边集合并到它的子结点因此堆需要支持合并操作合并到子结点的同时不能破坏当前结点处的边集因此堆还需要支持可持久化。这正是可持久化可并堆——其定义、性质与左偏树实现可参见 docs/ds/persistent-heap.md。该文档指出如果一种可并堆的时间复杂度不是均摊的那么可持久化后单次操作的时间复杂度就保证是 $O(\log n)$不会因特殊数据而退化。算法完整流程综合上述讨论得到完整的算法过程预处理从目标结点 $t$ 出发跑单源最短路求出最短路树 $T$建偏离边堆为最短路树上的每个结点构建对应的偏离边集合存储到可持久化可并堆里沿树下传沿着最短路树的边从目标结点 $t$ 开始将每个结点处的堆合并到子结点的堆里初始化从起始结点 $s$ 出发将该处的堆压入优先队列迭代弹出弹出队首的堆记录答案再将弹出堆顶后的堆压回优先队列并将堆顶边的终点处的堆压入优先队列。最后一步的进一步优化一般采用左偏树或随机堆实现可持久化可并堆此时最后一步还可以继续优化。这些堆的内部结构都是二叉树弹出堆顶后原本需要合并左右两个子结点再将合并后的堆顶压入优先队列。但在本算法中可以不执行合并操作直接将两个子结点对应的堆分别压入优先队列从而省去单次合并的 $O(\log m)$ 复杂度。由于每次弹出队首堆后至多会将三个新的堆压入优先队列左子堆、右子堆、堆顶边终点处的堆优先队列的大小是 $O(k)$ 的单次查询的时间复杂度因此降低到 $O(\log k)$。复杂度汇总阶段复杂度构建最短路树反向图单源最短路$O(m\log m)$构建可持久化可并堆插入全部偏离边$O(m\log m)$沿树下传合并堆$O(m\log m)$查询前 k 条答案$O(k\log k)$总复杂度$O(m\log m k\log k)$参考实现仓库提供了对应 Library Checker - K-Shortest Walk。该实现使用可持久化随机堆Persistent Randomized Heap作为可并堆核心结构如下// 可持久化随机堆 struct PersistentRandomizedHeap { static constexpr int N 1e7; int id; std::vectorint rt, lc, rc, to; std::vectorlong long va; int new_node(long long cost, int _to) { id; va[id] cost; to[id] _to; return id; } // 复制结点实现可持久化保留历史版本 int copy_node(int x) { id; lc[id] lc[x]; rc[id] rc[x]; va[id] va[x]; to[id] to[x]; return id; } // 随机堆合并复制根后按随机位决定左右子树 int meld(int x, int y, std::mt19937_64::result_type rand) { if (!x || !y) return x | y; if (va[x] va[y]) std::swap(x, y); x copy_node(x); if (rand 1) std::swap(lc[x], rc[x]); rc[x] meld(rc[x], y, rand 1); return x; } void insert(int i, long long cost, int _to) { rt[i] meld(rt[i], new_node(cost, _to), rng()); } void merge(int i, int j) { rt[i] meld(rt[i], rt[j], rng()); } };对照可持久化左偏树的合并过程见 docs/ds/persistent-heap.md选择权值更小的根、复制沿途路径、递归合并右子树随机堆在每次合并时通过随机数决定交换左右子树从而保证期望平衡同时copy_node保证每个版本的堆都完整保留满足「合并到子结点而不破坏当前结点边集」的可持久化需求。关键算法步骤的实现与文档描述一一对应// 构造偏离边并沿最短路树下传 void build_sidetracks() { for (int i 0; i m; i) { auto edge edges[i]; // 非树边out[edge.u] ! i且两端都在最短路树可达范围内 if (out[edge.u] ! i dist_t[edge.u] inf dist_t[edge.v] inf) { // 偏离成本 w h(v) - h(u) heaps.insert(edge.u, edge.c dist_t[edge.v] - dist_t[edge.u], edge.v); } } // 从根 t 开始 BFS沿树边把父结点堆合并到子结点下传边集 std::queueint q; q.push(t); while (!q.empty()) { auto cur q.front(); q.pop(); for (auto e : ig[cur]) { auto nxt edges[e].u; if (out[nxt] e) { // 该边是最短路树上的树边 heaps.merge(nxt, cur); q.push(nxt); } } } }// 在图 G 上求单源最短路得到前 k 条答案 void find_k_shortest_walks() { int cnt 0; ans.assign(k, -1); if (dist_t[s] inf) return; // s 到 t 不可达 ans[cnt] dist_t[s]; // 第 1 短最短路径本身 insert(heaps.rt[s], dist_t[s]); // 将 s 处的偏离边堆压入优先队列 while (!pq.empty() cnt k) { auto cost pq.top().first; int cur pq.top().second; pq.pop(); ans[cnt] cost; // 不合并直接分别压入左右子堆与堆顶边终点处的堆至多 3 个 insert(heaps.lc[cur], cost - heaps.va[cur]); insert(heaps.rc[cur], cost - heaps.va[cur]); insert(heaps.rt[heaps.to[cur]], cost); } }实现要点与文档结论的对应关系insert(x, cost)将某个非空堆以其堆顶调整后的成本压入优先队列成本计算公式为cost heaps.va[x]弹出堆顶cur后heaps.lc[cur]、heaps.rc[cur]分别是弹出堆顶后的左右子堆其成本修正为cost - heaps.va[cur]heaps.rt[heaps.to[cur]]是堆顶边终点处的堆成本直接沿用cost——这正是「至多压入三个新堆、无需合并」的优化落地第 1 短的答案就是最短路长度dist_t[s]随后每次弹出优先队列堆顶即得到一条新的 k 短路。应用场景与习题k 短路问题在竞赛编程中出现频率很高典型的变体包括带启发式剪枝的搜索优化A* 思想的直接应用、图上绕路路径计数与枚举、以及在含负权但无负环图上的推广等。OI-wiki 为此整理了一道经典习题「SDOI2010」魔法猪学院——考察对 k 短路算法实现细节的掌握注意题目要求的是路径数量与长度约束的联合计算需结合题意调整终止条件。参考资料与注释[Tutorial] k shortest paths and Eppsteins algorithm by meooow - Codeforces——偏离边sidetrack思想与 Eppstein 算法的经典讲解本文第二部分是其简化与工程化版本。可持久化可并堆——本文第二部分的底层数据结构含可持久化左偏树的完整推导与实现。A* 搜索算法——本文第一部分的搜索算法基础。Dijkstra 算法——两种解法共用的单源最短路预处理工具。图论基础概念路径——「路径」与「途径」术语辨析。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考