AOE 网与关键路径全题型秒杀与大题满分模板
【学长导读】 AOE 网(关键路径)是 408 数据结构图论章节的纯送分题(选择题 2 分,或大题结合拓扑排序考 5~8 分)。 很多同学做题慢、容易算错,是因为被课本里绕口的“事件最早、事件最迟、活动最早、活动最迟”四个概念绕晕了。 本笔记将草稿纸上的“左右填数秒杀法”与考卷上的“官方字母符号 & 大题踩分表格”做了一一映射,并为每个考法配齐了高清矢量结构拓扑图与历年真题/变式例题,看完直接闭眼拿满分!
💡 【核心认知】AOE 网的关键路径到底表达的是什么路径?(2020 年 408 真题第 8 题深度剖析)
==关键路径是从源点(起点)到汇点(终点)路径长度最长(各活动持续时间之和最大)的路径。==
1. 物理本质:它表达的是“决定整个工程完工的【最慢瓶颈路径】”
很多同学做题时直觉容易卡壳:“既然是希望工期越短越好,为什么关键路径反而是最长的路径,而不是最短的?”
- 工程并行的本质(木桶效应的反向理解):AOE 网中大量工序是并行推进的。工程要想彻底完工(到达汇点),必须等所有分支路径上的任务全部做完。
- 最慢分支卡死全局:哪怕其他支路只需 3 天就完工了,只要有一条支路需要 10 天,整个工程就必须等满 10 天才能交付验收。
- 最长路径 = 最短总工期:因此,从源点到汇点耗时最长的那条路径(各边权值之和最大),直接卡死了整个工程的完工下限。它的长度恰恰代表了完成整个工程所必需的【最短总工期】(工期绝不可能比瓶颈路径更快)。
- 容不得摸鱼的“关键”活动:分布在这条最长瓶颈路上的所有活动,时间余量均为零(),没有任何缓冲时间。任何一个活动拖延 1 天,整个工程就必须延期 1 天!这就是为什么它被称为**“关键”**路径。
2. 2020 年 408 统考第 8 题选项透彻拆解(考场防坑标杆)
【2020 统考 Q8 题干】 若使用 AOE 网估算工程进度,则下列叙述中正确的是( )。
A. 关键路径是从源点到汇点边数最多的一条路径
B. 关键路径是从源点到汇点路径长度最长的路径
C. 增加任一关键活动的时间不会延长工程的工期
D. 缩短任一关键活动的时间将会缩短工程的工期
【参考答案】:B
- A 选项错误(死穴陷阱):边数多 路径长!路径长度看的是边权值(持续时间)的代数和,不是边的条数。一条由 2 个耗时各 10 天的边构成的路径(长 20),远比由 5 个耗时各 1 天的边构成的路径(长 5)更长。
- B 选项正确(定义本源):关键路径的标准定义正是**“从源点到汇点路径长度最长的路径”**。
- C 选项错误(瓶颈必延误):关键路径是瓶颈主线,若增加任一关键活动的时间,瓶颈路径变得更长,工程总工期必然会被迫延长。
- D 选项错误(经典多关键路径陷阱):若 AOE 网中存在多条并行的关键路径(例如有两条长度同为 15 天的关键路径),单独缩短其中一条上的关键活动,另一条关键路径依然卡在 15 天,工程总工期毫无变化!要想缩短工期,必须同时缩短所有关键路径上的关键活动,或缩短它们共有的公共关键活动。
模块一:核心字母符号与草稿纸对照表(防蒙圈必背)
在 AOE 网中,圆圈(顶点)代表“事件(Vertex)”,箭头(有向边)代表“活动(Edge/Activity)”。
我们在草稿纸的每个圆圈旁画 [ 左数 , 右数 ],它们对应的官方符号和名字如下:
| 类别 | 官方符号 | 英文记忆法 | 官方中文名称 | 草稿纸对应位置 / 含义 |
|---|---|---|---|---|
| 圆圈(顶点/事件) | Vertex Earliest | 事件 的最早发生时间 | 圆圈旁的 【左数】(正推加法取最大) | |
| 圆圈(顶点/事件) | Vertex Latest | 事件 的最迟发生时间 | 圆圈旁的 【右数】(倒推减法取最小) | |
| 箭头(弧/活动) | Edge Earliest | 活动 的最早开始时间 | 直接等于 箭头起点圆圈的【左数】 | |
| 箭头(弧/活动) | Edge Latest | 活动 的最迟开始时间 | 等于 箭头终点圆圈的【右数】 弧长 | |
| 箭头(弧/活动) | Difference | 活动 的时间余量(松弛时间) | 最迟 最早 = 终点【右数】 起点【左数】 弧长 |
💡 一秒区分技巧:
- 带 (Vertex,顶点)的 都是指 圆圈(事件),也就是你在草稿纸圆圈旁填的
[左, 右]!- 不带 的 都是指 箭头(活动),需要用圆圈的数字算出来!
- (Earliest)永远代表“最早”(看左边),(Latest)永远代表“最迟”(看右边)!
- 事件和活动最早都是看左边(起始的),但最迟不一样
- 🔴对于活动的解读:箭头起点代表活动(开始最早,开始最迟),箭头重点代表活动(结束最早,结束最迟);所以活动最最迟开始就=结束最迟 -自身活动时间(弧长)
模块二:五大必背公式(大题卷面书写依据)
假设有一条活动(有向边),它从起点圆圈 指向 终点圆圈 ,边上的权重(持续时间/弧长)为 :
flowchart LR j(("圆圈 j<br>[ ve(j), vl(j) ]")) -->|"活动 a_i (耗时 weight)"| k(("圆圈 k<br>[ ve(k), vl(k) ]"))
1. 事件(圆圈)的最早发生时间 —— 【左数】
- 起点:
- 递推公式(从左往右算,所有指进来的箭头取最大值):
2. 事件(圆圈)的最迟发生时间 —— 【右数】
- 终点:(即工程总工期)
- 递推公式(从右往左倒推,所有发出去的箭头取最小值):
3. 活动(箭头)的最早开始时间
- 公式名称:活动最早开始时间公式
- 计算公式(谁发出箭头,就抄谁的左数):
4. 活动(箭头)的最迟开始时间
- 公式名称:活动最迟开始时间公式
- 计算公式(箭头指向谁,就用谁的右数减去边长):
5. 活动(箭头)的时间余量 (最核心考法!)
- 公式名称:活动时间余量公式(又称松弛时间公式)
- 计算公式:
- 考场秒记口诀:==“时间余量 = 尾右 头左 自身长”==(或者说:终右 - 始左 -自身长)
- 关键活动判定:当 (即 )时,活动 为关键活动!由关键活动连接而成的从源点到汇点的路径即为关键路径。
模块三:草稿纸 30 秒做题流程(总体破题思路)
拿到任何一道 AOE 网题目,脑子里不要乱想,严格按以下三步走:
- 第一步(正推填左数 ):
- 起点标
[0, ]。 - 顺着箭头往右加边长;遇到多个箭头汇入同一个圆圈,谁算出来大就填谁,直到算出终点的左数(即总工期)。
- 起点标
- 第二步(倒推填右数 ):
- 终点的右数直接照抄左数(如
[12, 12])。 - 逆着箭头往左减边长;遇到一个圆圈分叉发出多个箭头,谁算出来小就填谁,一路退回起点
[0, 0]。
- 终点的右数直接照抄左数(如
- 第三步(按需套公式):
- 问某条边的时间余量:直接用 终点右数 起点左数 边长。
- 问关键路径:找所有满足 终点右数 起点左数 边长(即余量为 )的边,串起来就是关键路径!
模块四:大题试卷规范写法(面向阅卷老师的满分踩分模板)
⚠️ 注意:如果在大题(应用题)中考到求关键路径、事件最早/最迟时间、活动最早/最迟时间及时间余量,最标准、最省时间且阅卷老师最喜欢的满分写法是【列表法】!
【母题题干】
已知包含 6 个事件()和 10 个活动()的 AOE 网,拓扑结构与每个顶点的 [最早 ve, 最迟 vl] 标注如下:

求:(1)各事件的最早与最迟发生时间;(2)各活动的最早开始时间、最迟开始时间及时间余量;(3)关键路径、总工期及时间余量最大的活动。
【试卷规范写法(满分踩分模板)】
解:
(1)计算各事件的最早发生时间 与最迟发生时间 : 由公式 及 ,列表计算如下:
| 事件(顶点 ) | ||||||
|---|---|---|---|---|---|---|
| 最早发生时间 | ||||||
| 最迟发生时间 |
(注:大题若分值较高,可在表下附关键步骤方程保底:)
(2)计算各活动的最早开始时间 、最迟开始时间 及时间余量 : 由公式 ,,,列表计算如下:
| 活动 | 弧 | 权值 | 时间余量 | 是否关键活动 | ||
|---|---|---|---|---|---|---|
| 否 | ||||||
| 是 | ||||||
| 否 | ||||||
| 否 | ||||||
| 是 | ||||||
| 否 | ||||||
| 否 | ||||||
| 否 | ||||||
| 是 | ||||||
| 否 |
(3)结论:
- (或写为顶点序列 )
模块五:408 命题人全考法与变式例题全集(含高清图解)
考法 1:求某个活动的时间余量 / 最早 / 最迟时间
【经典例题 1-1】(2013 年 408 统考真题第 6 题)
已知某工程的 AOE 网拓扑结构如下图所示:

求:活动 和 的时间余量各是多少?
- 秒杀解析:
- 正推计算终点 9 的工期为 天;红色粗边路径 为关键路径。
- 倒推各节点 :
- 顶点 2 为
[3, 3],顶点 5 为[6, 7]; - 顶点 3 为
[2, 5],顶点 6 为[6, 9]。
- 顶点 2 为
- 套用秒杀公式
时间余量 = 尾右 - 头左 - 边长:- 活动 :
- 活动 :
考法 2:找关键路径与避开“全等点”陷阱
【考题特征与避坑核心】
🚨 高频死穴:很多同学误以为“只要连接两个 顶点的边,就必定是关键活动”。这是致命大坑!
- 以母题中的活动 为例:
- 起点 3 满足 (在关键路径上);
- 终点 6 满足 (在关键路径上);
- 两个圆圈都是关键事件,但活动 的时间余量为:
- 它不仅不是关键活动,反而是全图余量最大的“摸鱼活动”!
- 【考场铁律】:判断关键路径,不要只看圆圈,必须严格验算:!
考法 3:通过加快关键活动缩短总工期(定性/定量考法)
【经典例题 3-1】(双关键路径协同压缩模型)
已知某 AOE 网存在两条平行的关键路径,工期均为 15 天:

-
问 1:只压缩活动 的工期 2 天,总工期能否变为 13 天?
- 答案:不能!
- 原因:关键路径有两条( 和 ),单压缩 ,另一条依然是 15 天,总工期毫无变化。
- 铁律:多条关键路径必须“同时压缩”或者“压缩所有关键路径共享的公共边”!
-
问 2:若同时压缩 和 的工期,最多能压缩几天?
- 答案:最多压缩 3 天!
- 原因:图中存在非关键旁路 天。当 和 共同压缩 3 天后,总工期降到 天,此时旁路 也变成了关键路径!若再继续压缩 和 , 就会卡死总工期,单压 将不再起效。
- 铁律:关键活动的最大有效压缩量,等于平行非关键旁路的时间余量!
考法 4:结合拓扑排序序列考算法实现原理
【考题模型与概念识别】
408 选择题常将 AOE 网与拓扑排序(AOV 网)交织在一起考察底层算法:
sequenceDiagram participant Topo as 拓扑有序序列 participant InvTopo as 逆拓扑有序序列 Note over Topo: 从源点向汇点依次推进 Topo->>Topo: 计算各个顶点的最早发生时间 ve(k) [填左数] Note over InvTopo: 从汇点向源点逆向倒退 InvTopo->>InvTopo: 计算各个顶点的最迟发生时间 vl(k) [填右数]
【经典例题 4-1】(概念秒杀题)
在求 AOE 网的关键路径时,关于各事件最早发生时间 和最迟发生时间 的计算顺序,下列说法正确的是( )。
A. 按逆拓扑次序计算, 按拓扑次序计算
B. 按拓扑次序计算, 按逆拓扑次序计算
C. 两者均按拓扑次序计算
D. 两者均按逆拓扑次序计算
- 【秒杀答案】:B
- 【口诀牢记】:“正推加法走拓扑,倒推减法逆拓扑!”
模块六:考场终极秒杀自查口诀(直接背诵)
圈填左右两数据,正推拓扑左边立;
箭头汇合加法算,多路取大莫迟疑;
终点右数抄左数,逆拓倒推减法去;
箭头分叉取最小,回退直到零归位;
活动最早抄头左,活动最迟尾右减;
尾右减去头左数,再扣身长得余量;
余量为零是关键,最长路径工期全;
双路并跑同时压,旁路余量定上限!