引言很多同学学完拓扑排序只会用它给活动排个先后次序。但工程里真正被追问的是另一件事整个项目最早什么时候能干完哪些活儿一天都拖不得前者是“最长路”后者是“关键路径Critical Path”。拓扑排序解决的是“能不能排”、解决“依赖是否合法”关键路径在它之上再叠一层带权最长路的推导是信奥提高组图论里非常经典、也极易踩坑的一个综合考点。本文用一个校园科技节筹备排期的原创题把概念、推导、双语言实现、易错点和进阶一次讲透。一、题目与项目目标原创题校园科技节筹备排期学校要筹备科技节把所有筹备工作拆成了若干个“事件里程碑”。规定一共有n个事件编号1..n。事件1是“项目开工”事件n是“项目竣工”。有m条筹备活动用有向边u → v表示权重w是该活动的工期天数w ≥ 0。含义是事件u完成之后活动u→v才能开工开工后需要w天。只要前置事件已全部完成多个活动可以并行推进。求两件事整个科技节筹备的最早完成天数哪些活动是关键活动——它只要晚开工 1 天整个项目就会晚 1 天即“松弛时间为 0”的活动。这就是经典的AOE 网Activity On Edge边表示活动关键路径问题。二、核心考点拓扑排序 判环有向图若出现环说明依赖自相矛盾根本排不了期必须先检测。事件最早发生时间ve在拓扑序上正向递推本质是求“带权 DAG 最长路”。事件最迟发生时间vl在逆拓扑序上反向递推用min松弛。关键活动判定对边u→v工期w最早开工e ve[u]最迟开工l vl[v] − w当e l松弛时间 0时该活动关键。多汇点处理用“超级汇点”把多个出度为 0 的节点统一收口否则vl会被全局最长时间撑大、误判关键活动。关键路径还原顺着关键活动把所有关键路径走出来关键路径可能不止一条。三、解法与拆解3.1 拓扑排序 判环用 Kahn 算法统计入度入度为 0 的入队每次弹出并消减后继入度。若最终排进拓扑序列的节点数不等于总节点数说明有环直接返回“无关键路径”。3.2 正向求 ve最早发生时间 最长路初始化所有ve 0。按拓扑序遍历每个节点u用它的每条出边u→v权 w去松弛ve[v] max(ve[v], ve[u] w)因为拓扑序保证u一定在v之前被处理完等u的所有前驱都松弛过之后ve[u]已经是“从开工到u的最长耗时”于是ve[v]自然收敛为“到v的最长耗时”。整个项目的最早完成时间T max(ve)也就是所有“终点事件”里最晚的那个。为了把多个终点统一成一个我们引入超级汇点n1把所有“出度为 0”的节点连一条权重 0 的边到n1。这样ve[n1]就等于全局最早完成时间T后面求vl也不用特殊判断了。3.3 反向求 vl最迟发生时间初始化所有vl T。按逆拓扑序遍历每个节点u用它的每条出边u→v权 w去松弛vl[u] min(vl[u], vl[v] − w)含义事件u最迟必须在vl[v] − w之前发生才不耽误后继v的最迟发生。vl从终点往回推所以必须逆拓扑序。3.4 关键活动判定与路径还原对每条原边u→v权 w该活动最早开工e ve[u]该活动最迟开工l vl[v] − w若e l说明它没有一点缓冲是关键活动否则它的松弛时间就是l − e。把所有关键活动收集起来从“开工且ve 0”的起点顺着关键边走就能还原出一条或多条关键路径。四、时间 / 空间复杂度时间复杂度拓扑排序O(n m)正向ve与反向vl各扫一遍所有边O(n m)合计O(n m)。空间复杂度邻接表、入度、拓扑序、ve、vl各O(n m)边主导即O(n m)。注意ve、vl用long long工期累加可能很大权值非负最长路有定义。五、易错点重点有环不判直接递推会死循环或结果错误必须先拓扑排序并校验节点数有环则本题无解。多汇点必须接超级汇点若不处理多个“出度为 0”的终点它们的vl会被初始化成全局T而偏大从而把本不关键的活动误判为关键。接一个权重 0 的超级汇点最稳妥。ve 是取max最长路不是min求“最早完成”本质是 DAG 最长路和最短路的min正好相反别写反。vl 必须逆拓扑序 取min顺序错了vl[v]还没定下来就去松弛vl[u]结果必然错。关键活动判定用ve[u] vl[v] − w不是ve[u] vl[u]活动在边上、工期在点之间混淆节点时间和边时间是最常见的笔误。关键路径可能不止一条还原时要把所有满足e l的边都收集不能找到一条就停。工期必须非负出现负权时“最长路”无定义会变成求环NP-hard建图时就要保证w ≥ 0。六、进阶AOE 与 AOV 的区别本文是 AOE边活动权工期AOV 是“点活动、边先后约束、点不带权”AOV 通常只做拓扑排序不谈关键路径。输出所有关键路径在关键活动子图上做 DFS把每条从起点到终点的关键路径都打印出来。与资源约束结合PERT / 项目调度若同一时刻能干活的人数有限关键路径只是“理想并行下界”真实工期还要受资源限制那是更复杂的 RCPSP 问题一般 NP-hard。练习推荐洛谷P1113 杂务是关键路径裸题P1238等可作巩固。把本文代码稍作改造即可直接套。与最短路对照记忆最短路d[v] min(d[v], d[u] w)正向、关键路径ve[v] max(...)正向、vl反向min三者放在一起对比考试时不晕。七、小结与互动拓扑排序负责“能不能排”关键路径负责“排完要多久、哪里不能拖”。掌握ve / vl / el三步再记住超级汇点和逆序求 vl两个坑这道题在提高组里就是送分题。你刷题时还遇到过哪些“拓扑排序之后还能再进阶”的题型欢迎在评论区聊聊下一篇我们可以写“差分约束与关键路径的亲戚关系”。参考代码C 实现#include bits/stdc.h using namespace std; // 返回 (T, 关键活动列表)有环则 T -1 pairlong long, vectortupleint, int, long long criticalPath( int n, const vectortupleint, int, long long edges) { vectorvectorpairint, long long g(n 2); // 1..n 超级汇点 n1 vectorint indeg(n 2, 0); for (auto e : edges) { int u get0(e), v get1(e); long long w get2(e); g[u].push_back({v, w}); indeg[v]; } // 超级汇点把出度为 0 的节点都连到 n1权 0统一成单汇点 for (int i 1; i n; i) if (g[i].empty()) { g[i].push_back({n 1, 0}); indeg[n 1]; } // Kahn 拓扑排序 queueint q; for (int i 1; i n 1; i) if (indeg[i] 0) q.push(i); vectorint topo; vectorint deg indeg; while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (auto pr : g[u]) if (--deg[pr.first] 0) q.push(pr.first); } if ((int)topo.size() ! n 1) return {-1, {}}; // 有环 vectorlong long ve(n 2, 0); for (int u : topo) for (auto pr : g[u]) ve[pr.first] max(ve[pr.first], ve[u] pr.second); long long T ve[n 1]; // 全局最早完成 vectorlong long vl(n 2, T); for (auto it topo.rbegin(); it ! topo.rend(); it) { int u *it; for (auto pr : g[u]) vl[u] min(vl[u], vl[pr.first] - pr.second); } vectortupleint, int, long long critical; for (auto e : edges) { int u get0(e), v get1(e); long long w get2(e); if (ve[u] vl[v] - w) critical.push_back(e); // 松弛时间 0 } return {T, critical}; }Python 实现from collections import deque def critical_path(n, edges): n: 事件数 (1..n) edges: list of (u, v, w) 返回 (T, 关键活动列表)有环返回 (None, None) g [[] for _ in range(n 2)] # 1..n 超级汇点 n1 indeg [0] * (n 2) for u, v, w in edges: g[u].append((v, w)) indeg[v] 1 for i in range(1, n 1): # 出度为 0 的连到超级汇点 if not g[i]: g[i].append((n 1, 0)) indeg[n 1] 1 # Kahn 拓扑排序 deg indeg[:] q deque([i for i in range(1, n 2) if deg[i] 0]) topo [] while q: u q.popleft(); topo.append(u) for v, w in g[u]: deg[v] - 1 if deg[v] 0: q.append(v) if len(topo) ! n 1: return None, None # 有环 ve [0] * (n 2) for u in topo: for v, w in g[u]: ve[v] max(ve[v], ve[u] w) T ve[n 1] vl [T] * (n 2) for u in reversed(topo): for v, w in g[u]: vl[u] min(vl[u], vl[v] - w) critical [(u, v, w) for u, v, w in edges if ve[u] vl[v] - w] return T, critical样例演示输入n6边u v w1 2 3 1 4 4 2 3 2 2 5 3 3 6 5 4 3 1 4 5 1 5 6 4推导结果各事件最早发生ve事件10事件23事件44事件35事件56事件610最早完成T 10天。各事件最迟发生vl事件610事件56事件35事件44事件23事件10。关键活动松弛时间 01→2、1→4、2→3、2→5、3→6、4→3、5→6。非关键活动4→5其最早开工4、最迟开工5有 1 天松弛可晚 1 天开工不影响整体。关键路径长度均为 101→2→3→6、1→2→5→6、1→4→3→6。可见即使4→5这条活动晚一天项目仍能按时完成而其它任何一条关键活动晚一天整体就晚一天。这正是关键路径想告诉项目经理的事。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。