如何找到第 K 短的路径？——从 Dijkstra 到 Yen 算法

Dijkstra 和反向 Dijkstra 到底分别在什么场景下使用图中的第 K 短路径要怎么找如果允许重复经过节点或者要求路径不能重复经过节点处理方式有什么不同当路径还带有等待时间约束时算法又该如何改造本文会通过四类题型由浅入深地讲解这些问题。一、标准 Dijkstra 算法的描述和应用Dijkstra 算法是用来求解非负权图上的单源最短路径问题的经典方法从一个源点出发求它到图中其余节点的最短距离。有向图和无向图都可以使用但只要存在负权边Dijkstra 的贪心性质就不再成立这时需要使用到 Bellman-Ford 算法但这已经超出本文的讨论范围。在具体实现上我们维护一个dist数组dist[v]表示当前已经找到的、从起点到节点v的最短距离上界。在算法运行过程之中这个值可能经过多次松弛而逐渐变小。可以把 Dijkstra 类比成将普通 BFS 的先进先出队列换成按照当前路径长度排序的优先队列更准确地说它每次选取暂定距离最小的状态(distance, u)再遍历u的所有邻边。如果经过u能让相邻节点v的距离变得更小就更新dist[v]这一过程称为松弛。由于所有边权都非负一个没有过期的状态从堆顶弹出时对应节点的最短距离就可以确定下来。先以 UVa 423 - MPI Maelstrom 为例看一下堆优化 Dijkstra 的代码实现题目给定由 n 个处理器组成的网络拓扑边权代表相邻处理器之间的通信耗时。一个处理器收到消息之后可以立即向所有与它直接相连的处理器发送消息并且多个处理器可以同时发送。因此消息最早到达处理器i的时间就是从处理器1到i的最短距离等到所有处理器都收到消息时花费的总时间就是这些最短距离中的最大值。输入格式第一行输入整数 n处理器数量满足 1 ≤ n ≤ 100。后续输入描述一个 n × n 的邻接矩阵 A其中 A(i,j) 代表从处理器 i 直接向处理器 j 发送消息的通信开销若输入为字符x则表示二者之间没有直接连接。节点向自身发送消息不需要网络传输因此 A(i,i)0。网络为无向图满足 A(i,j)A(j,i)。输入仅给出邻接矩阵严格下三角部分第 2 行1 个数据 A(2,1)第 3 行2 个数据 A(3,1), A(3,2)输出格式从 1 号处理器向所有其他处理器广播消息所需的最短时间。输入样例5 50 30 5 100 20 50 10 x x 10输出样例35这一道题目可以采用标准 Dijkstra 算法解决。我们用邻接表存图用一维数组记录处理器1到每个节点的当前最短距离再使用小根优先队列按照距离从小到大扩展状态。最后取dist[1...n]的最大值就是完成广播所需的最短时间。给出如下的完整代码#include bits/stdc.h using namespace std; using ll long long; const ll INF numeric_limitsll::max() / 4; using pli pairll, int; struct Edge { int to; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorvectorEdge graph(n1); //邻接表方式存储图 for (int i2;in;i) { for (int j1; ji;j) { string value; cinvalue; if (value!x) { ll weight stoll(value); graph[i].push_back({j, weight}); graph[j].push_back({i, weight}); } } } priority_queuepli, vectorpli, greaterpli pq; vectorll dist(n1, INF); dist[1] 0; pq.push({0, 1}); while (!pq.empty()) { auto [distance, u] pq.top(); pq.pop(); if (distance ! dist[u]) continue; for (const auto e : graph[u]) { int v e.to; if (dist[v] distance e.w) { dist[v] distance e.w; pq.push({dist[v], v}); } } } ll ans 0; for (int i1;in;i) ans max(ans, dist[i]); cout ans endl; return 0; }相关解释vectorvectorEdge graph(n1);使用邻接表存图并采用从 1 开始的节点编号。graph[i]存放所有从节点i出发的边无向边需要分别加入两个方向。有向图和无向图都可以使用邻接表只是加边方式不同。vectorll dist(n1, INF);则记录从起点到各节点当前已知的最短距离。priority_queuepli, vectorpli, greaterpli pq;定义了小根优先队列。每个元素的含义是{从起点到当前节点的距离, 当前节点编号}队列先比较距离距离相同时再比较节点编号。Dijkstra 真正依赖的是距离较小的状态先出队节点编号只负责在距离相同时确定一个稳定的先后顺序不会影响最短距离的正确性。for (const auto e : graph[u])遍历节点u的所有邻边。若distance e.w dist[v]说明经过u到达v更短此时更新dist[v]并把新状态加入优先队列。if (distance ! dist[u]) continue;用来跳过过期状态。比如队列中先后出现{10,u}和{7,u}当{10,u}出队时dist[u]已经被更新为 7那么距离 10 的状态就没有继续扩展的必要。这里不是说节点u只能处理一次而是只处理与当前最优记录一致的状态。在绝大多数稀疏图中邻接表加小根优先队列都是最常用也最稳妥的实现。采用上面这种允许同一节点多次入堆、出队时跳过旧状态的写法时堆中最多可能出现 O(E) 个状态因此也可以把复杂度写成 O((VE)log E)。对于普通简单图E ≤ V²所以通常简写为 O((VE)log V)。空间复杂度为 O(VE)。邻接表加优先队列属于堆优化 Dijkstra尤其适合边数远小于 V² 的稀疏图。为了对照另一种写法接下来看 POJ 2387 - Til the Cows Come Home。题目给定一个正权无向图节点数量满足 2 ≤ V ≤ 1000边数量满足 1 ≤ E ≤ 2000要求节点 V 到节点 1 的最短距离。输入格式第1行两个整数E和V即先给定边数再给定顶点数目第2到E1行每行描述一条道路包含三个用空格分隔的整数。前两个整数表示道路连接的地标编号第三个整数表示道路长度范围1到100输出格式一个整数表示贝茜从 V 号地标到 1 号地标必须行走的最短距离。输入样例5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100输出样例90完整代码如下#includebits/stdc.h using namespace std; using ll long long; const ll INF numeric_limitsll::max() / 4; int main() { ios::sync_with_stdio(false); cin.tie(0); int E, V; cin E V; vectorvectorll graph(V1,vectorll(V1,INF)); for (int i0;iV;i) graph[i][i] 0; for (int i0;iE;i) { int u, v, w; cin u v w; graph[u][v] min(graph[u][v],(ll)w); graph[v][u] min(graph[v][u],(ll)w); } vectorll dist(V1,INF); vectorbool used(V1,false); dist[V]0; for (int iter1;iterV;iter){ int u-1; for (int i1;iV;i){ if (!used[i] (u-1 || dist[i]dist[u])){ ui; } } if (u-1||dist[u]INF) break; used[u]true; for (int v1;vV;v){ if (!used[v]graph[u][v] ! INF) { if (dist[u]graph[u][v] dist[v]) dist[v] dist[u] graph[u][v]; } } } cout dist[1] endl; return 0; }这道题目还需要处理重边。比如输入之中可能同时存在1 2 20 1 2 15采用邻接矩阵时同一对节点之间只需要保留最短的那条边graph[u][v] min(graph[u][v], (ll)w); graph[v][u] min(graph[v][u], (ll)w);dist[i]的含义仍然是从起点 V 到节点i当前已知的最短距离初始化为INF表示暂时无法到达。每一轮通过线性扫描找到一个尚未确定、且dist最小的节点u再用dist[u] graph[u][v]松弛其他节点。由于边权非负u被选中之后它的最短距离就可以确定下来。上述代码展示的是 Dijkstra 的朴素实现时间复杂度为 O(V^2)空间复杂度也是 O(V^2)。需要说明的是POJ 2387 本身只有至多 2000 条边实际上属于稀疏图使用邻接表加优先队列会更合适这里只是借它规模不大的数据展示邻接矩阵版本。当 E 接近 V^2 时图才是真正的稠密图此时邻接矩阵结合线性扫描往往更直接也可能比频繁维护堆更快。选择实现方式时应该先看 E 与 V^2 的关系而不是默认某一种写法永远更优。二、A* 算法和第 K 短路径在标准 Dijkstra 算法之中dist数组只为每个节点保留一个最优值。但是如果我们需要找的不是最短路径而是第 K 短路径这时候应该如何处理呢一个直接的想法是不再让每个节点只出队一次而是统计它第几次从优先队列中取出。对于正权图第 1 次取出节点u对应到达u的最短路径第 2 次对应第二短依次类推。这个方法能够求允许重复经过节点和边的第 K 短路但如果直接按照已经走过的距离扩展优先队列中会出现大量最终到不了终点、或者明显偏离终点的状态。A* 的作用就是利用“距离终点还剩多远”来调整扩展顺序尽量少搜索无关区域。下面以 POJ 2449 - Remmarguts Date 为例。题目大意是在有向正权图中求从起点 S 到终点 T 的第 K 短路径长度。路径允许重复经过节点和边长度相同但经过方式不同的路径也分别计数如果不存在第 K 短路径则输出-1。输入格式第一行包含两个整数N和M1 ≤ N ≤ 10000 ≤ M ≤ 1000000。站点编号从1到N。随后M行每行包含三个整数A、B和T1 ≤ A,B ≤ N1 ≤ T ≤ 100表示存在一条从A站点到B站点的单向小路耗时为T。最后一行包含三个整数S、T和K1 ≤ S,T ≤ N1 ≤ K ≤ 1000。输出格式单独一行输出一个整数表示第 K 短路径的长度不存在则输出-1。输入样例4 5 1 2 2 1 3 5 2 4 3 3 4 1 2 3 1 1 4 3输出样例6这里可以引出 A* 算法。它是一种启发式最短路径搜索算法核心思想是在 Dijkstra 的基础上再给每一个状态加上“从当前节点到终点还需要多少代价”的估计。标准 Dijkstra 只按照起点到当前节点的距离排序行为就像以起点为圆心不断向外扩散A* 则同时考虑已经走了多远以及距离目标还可能有多远因此会优先扩展更有希望较早到达终点的状态。A* 会给每个待搜索状态计算评价函数f(n) g(n) h(n)。其中g(n)表示从起点 S 到节点 n 已经付出的实际代价h(n)表示从节点 n 到终点 T 的估计代价搜索时优先取出f(n)更小的状态。值得注意的是标准 Dijkstra 可以看成h(n)0的特殊情况。为了保证搜索顺序的正确性启发函数通常要求不能高估真实距离并且在满足此条件下启发函数越接近真实值A*算法搜索效率和正确率也就越高扩展的无效节点也就越少。也就是需要满足以下两个条件可容许性对任意节点nh(n)不能大于从n到终点的真实最短距离。即h(n) ≤ d(n,target)其中d(n, target)是节点n到终点的真实最短距离。这是为了保证A*找到的是真正的最短路径。一致性对于任意边W(a,b)满足h(a) \leq w(a,b) h(b)其中w(a,b)是a 到b的权值。这是可容许行更强的条件。而在这道题中我们直接在反图上从终点执行一次 Dijkstra得到原图中每个节点到终点的真实最短距离。也就是说这里的h(n)不是大概估计而是一个精确的启发函数。为什么要建反图原图中的边是u - v反图中就存成v - u。从终点 T 在反图上运行 Dijkstra得到的h[u]恰好就是原图中从u到 T 的最短距离。若h[u]为无穷大说明从u根本无法到达终点这类状态可以直接剪掉。#include functional #include iostream #include limits #include queue #include vector using namespace std; using ll long long; using pli pairll, int; const ll INF numeric_limitsll::max() / 4; struct Edge { int to; int weight; }; struct State { int node; ll g; ll f; bool operator(const State other) const { if (f ! other.f) return f other.f; return g other.g; } }; ​ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorEdge graph(n 1); vectorvectorEdge reverseGraph(n 1); for (int i 0; i m; i) { int a, b, cost; cin a b cost; graph[a].push_back({b, cost}); reverseGraph[b].push_back({a, cost}); } int start, target, k; cin start target k; vectorll h(n 1, INF); priority_queuepli, vectorpli, greaterpli dijkstraQueue; ​ h[target] 0; dijkstraQueue.push({0, target}); ​ while (!dijkstraQueue.empty()) { auto [distance, u] dijkstraQueue.top(); dijkstraQueue.pop(); ​ if (distance ! h[u]) continue; ​ for (const Edge edge : reverseGraph[u]) { int v edge.to; ll newDistance distance edge.weight; ​ if (newDistance h[v]) { h[v] newDistance; dijkstraQueue.push({newDistance, v}); } } } ​ if (h[start] INF) { cout -1 \n; return 0; } if (start target) k; ​ priority_queueState, vectorState, greaterState open; vectorint popCount(n 1, 0); ​ open.push({start, 0, h[start]}); ​ while (!open.empty()) { State current open.top(); open.pop(); ​ int u current.node; popCount[u]; ​ if (u target popCount[u] k) { cout current.g \n; return 0; } ​ if (popCount[u] k) continue; ​ for (const Edge edge : graph[u]) { int v edge.to; if (h[v] INF || popCount[v] k) continue; ​ ll newG current.g edge.weight; open.push({v, newG, newG h[v]}); } } ​ cout -1 \n; return 0; }结构体State表示优先队列中的一个搜索状态把当前节点node、已经走过的实际距离g、预计经过终点时的总距离fgh放在一起。重载之后小根堆会优先取出f较小的状态若f相同再优先取出g较小的状态。建图时同时保存原图和反图。反向 Dijkstra 得到的h[i]表示原图中从节点i到终点的真实最短距离。它不仅给 A* 提供搜索方向也可以提前过滤h[v] INF的节点因为这些节点无论如何都无法走到终点。popCount[u]记录节点u已经有效出队多少次。与标准 Dijkstra 不同这里不能在第一次取出u后就永远丢掉其他到达方式因为第 2 次、第 3 次到达u的路径仍然可能组成最终答案。由于边权为正优先队列按照f扩展而终点处满足h[target]0所以终点第 K 次出队时对应的g就是第 K 短路径长度。open是 A* 的候选状态队列。每次取出f最小的状态遍历它的出边再把新的候选放回队列。它保存的是一条条路径状态而不是每个节点唯一的最短距离所以同一个节点可以在队列中出现多次真正限制有效扩展次数的是popCount。如果start target初始状态{start, 0, h[start]}会先把长度为 0 的空路径算作一次到达。但原题要求的是实际经过边的路径所以代码中需要先执行k把空路径跳过去。这里用反向 Dijkstra 求出的h[i]是精确最短距离不是估计值。它同时满足可容许性和一致性因此 A* 不仅能保证找到第 K 短路而且每个状态第一次出队时就是该节点在当前 g 下的最优扩展顺序。如果换成一个粗糙的估计函数虽然也可能正确但搜索效率会明显下降。这里求的是允许重复节点和边的第 K 短“游走”只是竞赛题中通常仍然简称为第 K 短路。不同路径即使长度相同也要分别计数所以优先队列中的重复状态不能简单去重。反向 Dijkstra 的复杂度为 O((NM)\log N)A* 阶段中每个节点最多有效扩展 K 次粗略上界可以写成 O(KM\log(KM))。启发函数主要减少实际扩展的无关状态但不会改变这里给出的最坏复杂度上界。三、Yen 算法思想和第 K 短简单路径上一道题允许重复经过节点和边因此同一个节点可以被多次扩展。但是如果题目要求路径中不能重复经过节点这种“统计终点第几次出队”的方法就不能直接使用了。下面介绍 UVa 1685 - Enjoyable Commutation这道题要求的正是第 K 短简单路径。题目给定一个带正权的有向图需要求从起点 a 到终点 b 的第 K 短路径满足一条路径不能重复经过同一个节点也就是必须是简单路径先按照路径总长度从小到大排序如果两条路径长度相同再按照节点序列的字典序排序如果不足 K 条路径输出None否则用连字符输出第 K 条路径经过的节点。每组数据的第一行包含n m k a b其中 2 \leq n \leq 501 \leq k \leq 200。接下来的 m 行每行给出一条有向边x y d。题目保证不存在自环同一对有序节点之间也不会出现重边。输入以五个 0 结束。输入样例5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 3 3 5 1 3 1 2 1 2 3 1 1 3 1 0 0 0 0 0输出样例1-2-4-3-5 1-2-3-4 None这道题可以采用 Yen 算法解决。Yen 算法先求出第一短的简单路径然后依次构造第二短、第三短直到得到第 K 短。假设当前已经确定的一条路径为1 - 2 - 4 - 6任何一条与它不同的新路径都一定存在一个“第一次发生偏离的位置”。这个位置可能在节点 1、节点 2也可能在节点 4。于是我们可以依次把这些节点当作偏离点将整条路径拆成两部分完整路径 rootPath spurPath其中rootPath是从起点到偏离点的公共前缀spurPath是从偏离点重新走向终点的后半段。为了让新路径既不同于已有答案又仍然是简单路径需要做两类限制禁止rootPath中偏离点之前的所有节点防止后半段绕回前缀并重复经过节点对所有与当前rootPath前缀相同的已有答案禁止它们在偏离点之后使用的那条边防止重新生成已经确定的路径。每个偏离点都可能产生一条候选路径这些候选不能在本轮结束后丢掉因为第一条路径产生的某个候选也可能直到第五轮才成为最优答案。所以代码使用一个全局候选集合candidates按照“总长度、节点序列字典序”排序。每一轮从中取出最小者作为下一条正式答案。还需要解决一个子问题在删除部分节点和边之后如何找到长度最短、且字典序最小的路径这里先在反图上从终点执行 Dijkstra得到dist[u]表示节点u到终点的最短距离。然后从起点正向恢复路径每一步在所有满足dist[u] w(u,v) dist[v]的邻边中选择终点编号最小的一个。距离条件保证最终仍然是最短路径邻接点从小到大选择则保证节点序列的字典序最小。完整代码如下#include bits/stdc.h using namespace std; ​ using ll long long; const ll INF (1LL 62); ​ struct Edge { int to; int w; }; ​ struct Path { ll dist; // 路径总长度 vectorint nodes; // 路径上的节点序列 }; ​ struct PathCmp { bool operator()(const Path a, const Path b) const { if (a.dist ! b.dist) return a.dist b.dist; return a.nodes b.nodes; } }; ​ int n, m, K, startNode, goalNode; vectorvectorEdge graphAdj, reverseAdj; vectorvectorint weightEdge; ​ bool shortestPath( int source, int target, const vectorchar bannedNode, const setpairint, int bannedEdge, Path result ) { if (bannedNode[source] || bannedNode[target]) return false; ​ vectorll dist(n 1, INF); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; ​ dist[target] 0; pq.push({0, target}); ​ while (!pq.empty()) { auto [currentDist, v] pq.top(); pq.pop(); ​ if (currentDist ! dist[v]) continue; ​ // 反图中的 v - u 对应原图中的 u - v。 for (const Edge e : reverseAdj[v]) { int u e.to; ​ if (bannedNode[u] || bannedNode[v]) continue; if (bannedEdge.count({u, v})) continue; ​ ll newDist currentDist e.w; if (newDist dist[u]) { dist[u] newDist; pq.push({newDist, u}); } } } ​ if (dist[source] INF) return false; vectorint nodes; nodes.push_back(source); ​ int current source; while (current ! target) { int nextNode -1; ​ // graphAdj[current] 已经按终点编号升序排列。 for (const Edge e : graphAdj[current]) { int v e.to; ​ if (bannedNode[v]) continue; if (bannedEdge.count({current, v})) continue; if (dist[v] INF) continue; ​ if (dist[current] (ll)e.w dist[v]) { nextNode v; break; } } ​ if (nextNode -1) return false; ​ nodes.push_back(nextNode); current nextNode; } ​ result.dist dist[source]; result.nodes move(nodes); return true; } ​ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ​ while (cin n m K startNode goalNode) { if (n 0 m 0 K 0 startNode 0 goalNode 0) { break; } ​ graphAdj.assign(n 1, {}); reverseAdj.assign(n 1, {}); weightEdge.assign(n 1, vectorint(n 1, -1)); ​ for (int i 0; i m; i) { int x, y, d; cin x y d; ​ graphAdj[x].push_back({y, d}); reverseAdj[y].push_back({x, d}); weightEdge[x][y] d; } for (int u 1; u n; u) { sort(graphAdj[u].begin(), graphAdj[u].end(), [](const Edge a, const Edge b) { return a.to b.to; }); } ​ vectorchar noBannedNode(n 1, false); setpairint, int noBannedEdge; ​ Path firstPath; if (!shortestPath(startNode, goalNode, noBannedNode, noBannedEdge, firstPath)) { cout None\n; continue; } ​ vectorPath answers; answers.push_back(firstPath); ​ // candidates 自动按照题目要求排序并且自动去重。 setPath, PathCmp candidates; ​ // 额外记录已成为答案的节点序列防止极端情况下重复加入。 setvectorint acceptedPaths; acceptedPaths.insert(firstPath.nodes); ​ while ((int)answers.size() K) { const Path previousPath answers.back(); int pathSize (int)previousPath.nodes.size(); ​ // rootCost 表示从起点到当前偏离点的前缀长度。 ll rootCost 0; ​ for (int spurIndex 0; spurIndex 1 pathSize; spurIndex) { int spurNode previousPath.nodes[spurIndex]; ​ // 当前根路径为 previousPath[0 ... spurIndex]。 vectorint rootPath( previousPath.nodes.begin(), previousPath.nodes.begin() spurIndex 1 ); ​ // 禁止根路径中除 spurNode 外的节点保证最终路径不重复访问节点。 vectorchar bannedNode(n 1, false); for (int i 0; i spurIndex; i) { bannedNode[rootPath[i]] true; } setpairint, int bannedEdge; ​ for (const Path path : answers) { if ((int)path.nodes.size() spurIndex) continue; ​ bool samePrefix true; for (int i 0; i spurIndex; i) { if (path.nodes[i] ! rootPath[i]) { samePrefix false; break; } } ​ if (samePrefix spurIndex 1 (int)path.nodes.size()) { bannedEdge.insert({ path.nodes[spurIndex], path.nodes[spurIndex 1] }); } } ​ Path spurPath; if (shortestPath(spurNode, goalNode, bannedNode, bannedEdge, spurPath)) { vectorint totalNodes rootPath; ​ // spurPath 的第一个节点就是 spurNode避免重复加入。 totalNodes.insert(totalNodes.end(), spurPath.nodes.begin() 1, spurPath.nodes.end()); ​ Path totalPath; totalPath.dist rootCost spurPath.dist; totalPath.nodes move(totalNodes); ​ if (!acceptedPaths.count(totalPath.nodes)) { candidates.insert(move(totalPath)); } } ​ int u previousPath.nodes[spurIndex]; int v previousPath.nodes[spurIndex 1]; rootCost weightEdge[u][v]; } ​ if (candidates.empty()) break; ​ auto it candidates.begin(); Path nextPath *it; candidates.erase(it); ​ acceptedPaths.insert(nextPath.nodes); answers.push_back(move(nextPath)); } ​ if ((int)answers.size() K) { cout None\n; } else { const vectorint result answers[K - 1].nodes; for (int i 0; i (int)result.size(); i) { if (i 0) cout -; cout result[i]; } cout \n; } } ​ return 0; }代码中有几个地方需要重点理解answers保存已经正式确定的路径candidates保存所有尚未被选中的候选路径。candidates定义在外层循环之外因此以前产生但暂时没有入选的路径会一直保留这正是 Yen 算法不能缺少的候选池。bannedNode只禁止根路径中spurNode之前的节点不禁止偏离点本身。否则无法从偏离点出发寻找新的后缀如果完全不禁前缀节点新后缀又可能绕回前面生成带重复节点的路径。bannedEdge需要检查所有已经进入answers的路径。只禁止上一条答案使用的边是不够的否则可能重新生成更早已经出现过的路径。shortestPath每次都在当前的禁点、禁边条件下重新求最短路。由于原题边权严格为正根据dist恢复路径时不会陷入零权环同时题目保证同一对有序节点之间至多一条边所以可以直接使用(u,v)表示一条被禁用的边并使用weightEdge[u][v]计算前缀长度。Yen 算法正确性的关键就在“第一次偏离”上。任意一条尚未进入答案集合的简单路径与某一条已有路径相比都可以找到第一个不同的边。枚举已有路径上的每个偏离点就不会漏掉它可能对应的候选而每次从全局候选池中取出排序最小的路径又保证了新加入answers的确实是下一条路径。一次shortestPath主要执行一次堆优化 Dijkstra复杂度约为 O((NM)\log N)。一条简单路径最多包含 N 个节点生成一条新答案时最多调用 O(N) 次最短路所以核心复杂度可以粗略写成 O(KN(NM)\log N)。当前代码为了判断相同前缀还会直接扫描已有答案最坏会额外产生 O(K^2N^2) 的前缀比较候选路径本身最多占用 O(KN^2) 的空间。在本题 N \leq 50、K \leq 200 的范围内这样的写法更直观也足以应对数据范围。四、另一种 K 短路允许重复经过节点并带有等待约束第二部分的 POJ 2449 已经允许重复经过节点和边这一部分真正增加的难点不是“允许重复”而是边的代价会随到达时间发生变化。下面以 UVa 1684 - Escape Plan 为例。题目中有 N 个星球编号为 0 到 N-1其中 0 是起点N-1 是终点。星球之间存在单向的超空间隧道每条隧道由四个整数U V C W描述隧道从U指向V通过隧道需要花费W秒隧道只会在时间 0,C,2C,3C,\dots 开放在任意一个星球上连续等待的时间不能超过T秒。有 K 艘帝国歼星舰会沿着较短的路线追击因此需要求从 0 到 N-1 的第 K1 短路径。路径允许重复经过节点和边花费时间相同的不同走法也要分别计数。如果不存在这样的路径输出-1。每组数据第一行包含N M K T满足 1 \leq N \leq 1000 \leq M \leq 5000 \leq K \leq 90 \leq T \leq 100。每条边的周期满足 1 \leq C \leq 10通过隧道的时间满足 1 \leq W \leq 10^6。输入以四个 0 结束。输入样例5 9 2 2 1 2 5 5 2 4 6 6 0 2 1 8 1 4 4 3 3 0 1 8 1 3 5 10 0 4 4 4 2 3 3 4 3 1 5 10 10 0 0 0 0 0 0 0输出样例Case 1: 28 Case 2: -1如果仍然只把“当前位于哪个节点”作为状态就会丢失必要的信息。比如同样到达节点u到达时间分别为 8 和 9面对一条每 3 秒开放一次的隧道接下来需要等待的时间并不相同。因此这里需要把状态写成(node, phase)其中phase是当前总时间对所有隧道周期最小公倍数的余数。因为 1 \leq C \leq 10所有周期的最小公倍数最多为lcm(1,2,...,10) 2520只要两个到达时间模period相同它们面对每一条隧道时的开放情况就完全相同。这样一来原本随绝对时间变化的问题就被展开成了至多 N \times 2520 个有限状态。假设当前时间对周期的余数为phase准备经过周期为cycle的边。距离最近一次可出发时间还需要等待int firstWait (cycle - phase % cycle) % cycle;但是不能只考虑最近的一次开放。如果firstWait cycle、firstWait 2 * cycle仍然不超过T主动多等一段时间也是合法选择并且可能影响后续边的开放时刻。所以代码需要枚举firstWait, firstWait cycle, firstWait 2 * cycle, ... T下面按照“完整行程”计数一次行程不只包含经过的隧道也包含每次等待之后选择的出发时刻。因此即使经过的节点序列相同只要等待安排不同产生的状态转移序列也不同代码会把它们分别保留。这个口径也解释了为什么不能只为一条边保留最近的开放时刻如果只按边序列区分路径则还需要另外去重。在展开后的状态图上所有转移代价都是wait cost并且严格大于 0因此仍然可以使用类似 Dijkstra 的小根堆。used[u][p]不表示这个状态是否访问过而是记录状态(u,p)已经第几次有效出队。相同状态最多扩展 K1 次如果它已经有 K1 种耗时不大于当前方案的到达方式那么后面的任意一段走法都可以分别接在这 K1 个前缀之后当前方案不可能再影响终点的前 K1 个答案。当终点第 K1 次出队时当前总时间就是答案。代码还在反图上做了一次普通 BFS提前标记哪些节点在拓扑上能够到达终点不能到达终点的分支无需进入优先队列。完整代码如下#include bits/stdc.h using namespace std; ​ typedef long long ll; ​ struct Edge { int to; int cycle; int cost; }; struct State { ll dist; // 从 0 号星球出发所用的总时间 int node; // 当前星球 int phase; // 当前时间模所有周期的最小公倍数 ​ bool operator(const State other) const { if (dist ! other.dist) return dist other.dist; if (node ! other.node) return node other.node; return phase other.phase; } }; ​ int gcd_int(int a, int b) { while (b ! 0) { int r a % b; a b; b r; } return a; } ​ int main() { ios::sync_with_stdio(false); cin.tie(NULL); ​ int N, M, K, T; int caseNo 1; ​ while (cin N M K T) { if (N 0 M 0 K 0 T 0) { break; } ​ vectorvectorEdge graph(N); vectorvectorint reverseGraph(N); int period 1; ​ for (int i 0; i M; i) { int u, v, c, w; cin u v c w; ​ graph[u].push_back(Edge{v, c, w}); reverseGraph[v].push_back(u); ​ period period / gcd_int(period, c) * c; } ​ vectorbool canReachTarget(N, false); queueint q; ​ const int target N - 1; canReachTarget[target] true; q.push(target); ​ while (!q.empty()) { int u q.front(); q.pop(); ​ for (size_t i 0; i reverseGraph[u].size(); i) { int v reverseGraph[u][i]; if (!canReachTarget[v]) { canReachTarget[v] true; q.push(v); } } } ​ const int need K 1; ll answer -1; ​ if (canReachTarget[0]) { // used[u][p]状态 (u,p) 已经从优先队列中弹出的次数 vectorvectorint used(N, vectorint(period, 0)); ​ priority_queueState, vectorState, greaterState pq; pq.push(State{0, 0, 0}); ​ int reachedTarget 0; ​ while (!pq.empty()) { State cur pq.top(); pq.pop(); // 前 need 次以后到达同一状态的路径不可能影响答案 if (used[cur.node][cur.phase] need) { continue; } used[cur.node][cur.phase]; ​ if (cur.node target) { reachedTarget; ​ if (reachedTarget need) { answer cur.dist; break; } } ​ for (size_t i 0; i graph[cur.node].size(); i) { const Edge e graph[cur.node][i]; ​ if (!canReachTarget[e.to]) { continue; } ​ int rem cur.phase % e.cycle; int firstWait (e.cycle - rem) % e.cycle; for (int wait firstWait; wait T; wait e.cycle) { ​ ll nextDist cur.dist wait e.cost; int nextPhase (cur.phase wait e.cost) % period; ​ if (used[e.to][nextPhase] need) { pq.push(State{nextDist, e.to, nextPhase}); } } } } } ​ cout Case caseNo : answer \n; } ​ return 0; }这份代码之中需要注意下面几个细节period period / gcd_int(period, c) * c逐步计算所有隧道周期的最小公倍数。因为每个c都不超过 10所以period最大只有 2520不会出现状态数量无限增长的问题。nextPhase可以直接通过(cur.phase wait e.cost) % period计算。虽然cur.phase不是完整的绝对时间但是所有边的周期都整除period因此保留这个余数已经足够决定后续所有等待时间。used[u][p]必须在状态出队时增加而不是在入队时增加。优先队列保证出队顺序按照总时间递增若在入队时就计数后加入但距离更短的合法状态可能会被过早剪掉。优先队列中可能存在dist、node、phase完全相同的多个状态这里不能像普通最短路那样去重。它们可能由不同的路径或者不同的隧道产生而题目要求这些走法分别计数。canReachTarget只根据图的连通关系进行剪枝。它为false时一定无法到达终点为true只表示拓扑上存在路径并不保证在等待上限之内一定可行真正的时间约束仍然要在状态转移时判断。题目给的是追兵数量 K要求的是第 K1 短路径所以代码使用need K 1。这一点和第二、三部分直接输入“第 K 条”并不一样。单条隧道的通过时间可达 10^6路径又允许绕环所以总时间使用long long存储。令 L 为所有周期的最小公倍数RK1。对于一条周期为 C_e 的边在一个时间相位下最多产生 \lfloor T/C_e\rfloor1 种等待方案。如果把展开图的边数记为令 L 为所有周期的最小公倍数RK1。对于一条周期为 Ce 的边在一个时间相位下最多产生 ⌊T/Ce⌋1 种等待方案。如果把展开图的边数记为/ppE ≤ L·Σsube∈E/sub(⌊T/Csube/sub⌋1)/pp那么多次出队 Dijkstra 的时间复杂度可以写成 O(RE·log(RE))。used数组的空间复杂度为 O(NL)如果把优先队列中的状态也计算在内最坏空间可以写成 O(NLRE)。代码在状态出队时现场枚举转移因此不需要显式建出整张展开图。这个上界比较松实际产生的候选状态数量仍然取决于图的结构。五、总结最后把本文几种容易混淆的模型放在一起比较问题类型路径是否允许重复节点状态中需要保留什么适合的做法单源最短路不作限制最短解可取简单路径当前节点Dijkstra第 K 短游走允许当前节点、到达次数反向 Dijkstra 计算启发函数再用 A* 多次扩展第 K 短简单路径不允许完整路径前缀与偏离位置Yen 算法 受限最短路带周期等待的第 K 短游走允许当前节点、时间相位、到达次数状态展开 多次出队的 Dijkstra所以遇到“第 K 短路”时第一件事不是直接套模板而是先确认题目中的“路径”到底是什么能不能重复经过节点和边相同长度的不同走法是否分别计数边权是否会随状态或时间变化。把这几个问题区分清楚之后应该使用 A*、Yen还是状态展开通常也就比较明确了。