一、核心概念
在 AOE 网(边表示活动 Activity On Edge)里:
- 顶点 = 事件(里程碑):不消耗时间,只是”这一刻,某些活动全部完成了”这个状态。
- 边 = 活动:消耗时间(权重 )。
每个顶点有两个时间参数:
| 符号 | 名称 | 含义 |
|---|---|---|
| 最早发生时间 | 所有指向 的活动全部做完, 这个事件最早能成立的时刻 | |
| 最迟发生时间 | 为了不拖累工期, 最晚必须成立的死线时刻 |
每条边(活动)有:
| 符号 | 含义 |
|---|---|
| (最早开始) | |
| (最迟开始) | |
| (时间余量) | ,也等于 |
的活动 = 关键活动; 的顶点 = 关键事件;关键活动首尾相连形成 关键路径,其总长 = 工程最短工期。
二、算法本身:怎么算才不会错
这是全篇最重要的一节。ve 和 vl 的计算方法是纯粹的”看箭头、列清单、取最值”,跟这个点是不是在关键路径上、是不是主干线完全无关。
2.1 算 (正向:源点 → 汇点,按拓扑序)
对每个顶点 :
- 在图上把所有”箭头尖头戳进 “的边,一条不漏地列出来(这一步最容易出错——人容易只记住自己心里那条”主线”,而漏掉旁支汇入的边)。
- 每条入边贡献一个候选值:起点的 + 该边权重。
- 。
为什么取 max(木桶原理):事件 要成立,必须它所有的前置活动都做完。哪怕 99 条入边都在时刻 3 完成,只要还有 1 条要到时刻 6 才完成, 就必须等到时刻 6 才能宣布”发生”。取最大值,是因为要等最慢的那个。
计算顺序要求:算 之前,它所有前驱顶点的 必须已经算出来(即按拓扑序推进)。
2.2 算 (反向:汇点 → 源点,按逆拓扑序)
对每个顶点 :
- 汇点(终点)的 = 汇点的 = 整个工程工期。
- 从汇点往回推,对每个顶点,把所有”从 出发的边”一条不漏地列出来。
- 每条出边贡献一个候选值:终点的 − 该边权重。
- 。
为什么取 min(死线倒逼): 后面接了好几条任务,每条任务都对 的完成时刻有一个”最晚不能超过几号”的要求。哪条任务的要求最紧(最早到期), 就必须满足哪条。取最小值,是因为要迁就最紧的那个。
2.3 一句话铁律
算 ve 只看入边,算 vl 只看出边;不管这个点在不在关键路径上,也不管它离主干线多远,只要图上画了一条边通向它/从它发出,这条边就必须被算进去。
三、顶点 6 的坑:ve(6) 到底是 3 还是 6?
这题之前反复算错,原因就是没有把”入边清单”摆全。
先看原图,把指向顶点 6 的边找全:
- ← 这条边很容易被漏看或漏算,是分歧的根源
只要原图上确实画了 ()这条边,那么按第二节的铁律,算 就必须把这条边也纳入候选:
如果漏看了 这条边,只用 一条边去算,就会错误地得到 。
通用排查方法:以后再遇到”这个点到底该算几”的分歧,不要靠回忆或直觉,而是:
- 圈出这个顶点;
- 把纸上/图上所有箭头指向它的边,用手指一条条点过去数一遍;
- 每条边都单独算一次候选值,最后统一取 max(算 ve)或 min(算 vl)。
漏边、漏箭头方向,是这类题目出错的头号原因,比公式记错更常见。
四、本题完整推导(把每一步”入边/出边清单”都摆开)
图的全部边(12 条活动):
1→3 (a=2) 1→2 (b=5) 1→4 (d=3)
3→4 (e=3) 3→6 (c=1)
4→2 (f=4) 4→6 (g=1) 4→5 (j=1) 4→7 (m=4)
2→5 (k=2)
6→7 (h=1)
7→5 (n=3)
4.1 正向算 ve(拓扑序:1 → 3 → 4 → 2、6 → 7 → 5)
| 顶点 | 入边清单(全部列出) | 候选值 | |
|---|---|---|---|
| 1(源点) | 无 | — | 0 |
| 3 | 2 | ||
| 4 | ; | ; | |
| 2 | ; | ; | |
| 6 | ; | ; | |
| 7 | ; | ; | |
| 5(汇点) | ;; | ;; |
→ 工程最短工期 = 12。
4.2 反向算 vl(逆拓扑序:5 → 2、7 → 4、6 → 3 → 1)
| 顶点 | 出边清单(全部列出) | 候选值 | |
|---|---|---|---|
| 5(汇点) | — | — | 12(= 工期) |
| 7 | 9 | ||
| 2 | 10 | ||
| 6 | 8 | ||
| 4 | ;;; | ;;; | |
| 3 | ; | ; | |
| 1(源点) | ;; | ;; |
五、事件(顶点)时间参数总表
| 事件 | 是否关键事件() | 原图标注 | ||
|---|---|---|---|---|
| 1 | 0 | 0 | 是 | 单数 0 |
| 3 | 2 | 2 | 是 | 单数 2 |
| 4 | 5 | 5 | 是 | 单数 5 |
| 6 | 6 | 8 | 否 | 双数 [6 / 8] |
| 2 | 9 | 10 | 否 | 双数 [9 / 10] |
| 7 | 9 | 9 | 是 | 单数 9 |
| 5 | 12 | 12 | 是 | 单数 12 |
顶点标注规范:关键事件()只写一个数字;非关键事件写 [ve / vl]。
六、活动(边)时间参数总表
余量公式:
| 活动 | 弧 | 关键活动? | ||||
|---|---|---|---|---|---|---|
| a | 1→3 | 2 | 0 | 2−2=0 | 0 | ✅ |
| b | 1→2 | 5 | 0 | 10−5=5 | 5 | |
| c | 3→6 | 1 | 2 | 8−1=7 | 5 | |
| d | 1→4 | 3 | 0 | 5−3=2 | 2 | |
| e | 3→4 | 3 | 2 | 5−3=2 | 0 | ✅ |
| f | 4→2 | 4 | 5 | 10−4=6 | 1 | |
| g | 4→6 | 1 | 5 | 8−1=7 | 2 | |
| h | 6→7 | 1 | 6 | 9−1=8 | 2 | |
| j | 4→5 | 1 | 5 | 12−1=11 | 6(全场最大) | |
| k | 2→5 | 2 | 9 | 12−2=10 | 1 | |
| m | 4→7 | 4 | 5 | 9−4=5 | 0 | ✅ |
| n | 7→5 | 3 | 9 | 12−3=9 | 0 | ✅ |
注意一个额外的坑:两个端点都是关键事件的边,不一定就是关键活动,还是要老老实实算一遍 是否为 0(本题没撞上这种情况,但下次遇到别偷懒跳过验证)。
关键路径:,长度 ,关键活动为 。
七、四问详解
(1) 最短工期 & 关键活动 最短工期 = 12;关键活动 = a、e、m、n(依据:见第六节, 的四条边)。
(2) 与活动 e 同时进行的活动有哪些?
方法: 是关键活动,固定占用区间 。其余每个活动的可行时间窗是 (起点最早能开始,终点最迟不能超过的时刻),若这个区间与 有内部重叠(非仅端点相切),则”可能同时进行”。
| 活动 | 窗口 | 与 是否重叠 |
|---|---|---|
| b (1→2) | 重叠 ✅ | |
| c (3→6) | 重叠 ✅ | |
| d (1→4) | 重叠 ✅ | |
| f (4→2) | 仅端点 5 相切,不算 | |
| g (4→6) | 仅端点 5 相切,不算 | |
| h (6→7) | 无交集 | |
| j,k,m,n | 均在 5 之后或本身是 e 平级的关键活动 | 无交集/不适用 |
→ 可能同时进行的活动:b、c、d。
(3) 时间余量最大的活动 查第六节表格, 值最大的是 j(4→5)= 6。
(4) b 从时刻 6 开始,如何保证不延期
- 顶点 2 的死线是 (不受 b 何时开始影响,因为工程总工期仍要求 12 不变)。
- b 在时刻 6 开始,要在 10 之前做完,最多能用 的时间。
- 若坚持不改 b 的时长(仍为 5),则顶点 2 实际发生时刻变为 (比原来的 9 晚了 2)。
- 顶点 2 之后只剩一条边 ,为了让顶点 5 仍在时刻 12 完成, 最多只能用 的时间。
- → 必须把活动 k 从原来的 2 压缩为 1,才能保证工程不延期。
八、速记口诀
【算点看箭头,两句话说完】
算 ve 只认"戳进来的箭头":起点 ve + 边权,逐条算,取 max(等最慢的);
算 vl 只认"射出去的箭头":终点 vl − 边权,逐条算,取 min(迁就最紧的)。
【防坑总纲】
算之前先把入边/出边"点名"点全,绝不凭主线印象;
两端点都关键 ≠ 这条边一定关键,d 该算还得算;
关键路径长度 = ve(汇点) = vl(汇点) = 工程总工期。