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 网题目,脑子里不要乱想,严格按以下三步走:

  1. 第一步(正推填左数 ):
    • 起点标 [0, ]。
    • 顺着箭头往右加边长;遇到多个箭头汇入同一个圆圈,谁算出来大就填谁,直到算出终点的左数(即总工期)。
  2. 第二步(倒推填右数 ):
    • 终点的右数直接照抄左数(如 [12, 12])。
    • 逆着箭头往左减边长;遇到一个圆圈分叉发出多个箭头,谁算出来小就填谁,一路退回起点 [0, 0]。
  3. 第三步(按需套公式):
    • 问某条边的时间余量:直接用 终点右数 起点左数 边长。
    • 问关键路径:找所有满足 终点右数 起点左数 边长(即余量为 )的边,串起来就是关键路径!

模块四:大题试卷规范写法(面向阅卷老师的满分踩分模板)

⚠️ 注意:如果在大题(应用题)中考到求关键路径、事件最早/最迟时间、活动最早/最迟时间及时间余量,最标准、最省时间且阅卷老师最喜欢的满分写法是【列表法】!

【母题题干】

已知包含 6 个事件()和 10 个活动()的 AOE 网,拓扑结构与每个顶点的 [最早 ve, 最迟 vl] 标注如下:

AOE网母题全貌图

求:(1)各事件的最早与最迟发生时间;(2)各活动的最早开始时间、最迟开始时间及时间余量;(3)关键路径、总工期及时间余量最大的活动。


【试卷规范写法(满分踩分模板)】

解:

(1)计算各事件的最早发生时间 与最迟发生时间 : 由公式 及 ,列表计算如下:

事件(顶点 )
最早发生时间
最迟发生时间

(注:大题若分值较高,可在表下附关键步骤方程保底:)

(2)计算各活动的最早开始时间 、最迟开始时间 及时间余量 : 由公式 ,,,列表计算如下:

活动弧 权值时间余量 是否关键活动
否
是
否
否
是
否
否
否
是
否

(3)结论:

  • (或写为顶点序列 )

模块五:408 命题人全考法与变式例题全集(含高清图解)


考法 1:求某个活动的时间余量 / 最早 / 最迟时间

【经典例题 1-1】(2013 年 408 统考真题第 6 题)

已知某工程的 AOE 网拓扑结构如下图所示:

2013年408真题第6题

求:活动 和 的时间余量各是多少?

  • 秒杀解析:
    1. 正推计算终点 9 的工期为 天;红色粗边路径 为关键路径。
    2. 倒推各节点 :
      • 顶点 2 为 [3, 3],顶点 5 为 [6, 7];
      • 顶点 3 为 [2, 5],顶点 6 为 [6, 9]。
    3. 套用秒杀公式 时间余量 = 尾右 - 头左 - 边长:
      • 活动 :
      • 活动 :

考法 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
  • 【口诀牢记】:“正推加法走拓扑,倒推减法逆拓扑!”

模块六:考场终极秒杀自查口诀(直接背诵)

圈填左右两数据,正推拓扑左边立;
箭头汇合加法算,多路取大莫迟疑;
终点右数抄左数,逆拓倒推减法去;
箭头分叉取最小,回退直到零归位;
活动最早抄头左,活动最迟尾右减;
尾右减去头左数,再扣身长得余量;
余量为零是关键,最长路径工期全;
双路并跑同时压,旁路余量定上限!