一、核心概念

在 AOE 网(边表示活动 Activity On Edge)里:

  • 顶点 = 事件(里程碑):不消耗时间,只是”这一刻,某些活动全部完成了”这个状态。
  • 边 = 活动:消耗时间(权重 )。

每个顶点有两个时间参数:

符号名称含义
最早发生时间所有指向 的活动全部做完, 这个事件最早能成立的时刻
最迟发生时间为了不拖累工期, 最晚必须成立的死线时刻

每条边(活动)有:

符号含义
(最早开始)
(最迟开始)
(时间余量),也等于

的活动 = 关键活动; 的顶点 = 关键事件;关键活动首尾相连形成 关键路径,其总长 = 工程最短工期。


二、算法本身:怎么算才不会错

这是全篇最重要的一节。ve 和 vl 的计算方法是纯粹的”看箭头、列清单、取最值”,跟这个点是不是在关键路径上、是不是主干线完全无关。

2.1 算 (正向:源点 → 汇点,按拓扑序)

对每个顶点 :

  1. 在图上把所有”箭头尖头戳进 “的边,一条不漏地列出来(这一步最容易出错——人容易只记住自己心里那条”主线”,而漏掉旁支汇入的边)。
  2. 每条入边贡献一个候选值:起点的 + 该边权重。
  3. 。

为什么取 max(木桶原理):事件 要成立,必须它所有的前置活动都做完。哪怕 99 条入边都在时刻 3 完成,只要还有 1 条要到时刻 6 才完成, 就必须等到时刻 6 才能宣布”发生”。取最大值,是因为要等最慢的那个。

计算顺序要求:算 之前,它所有前驱顶点的 必须已经算出来(即按拓扑序推进)。

2.2 算 (反向:汇点 → 源点,按逆拓扑序)

对每个顶点 :

  1. 汇点(终点)的 = 汇点的 = 整个工程工期。
  2. 从汇点往回推,对每个顶点,把所有”从 出发的边”一条不漏地列出来。
  3. 每条出边贡献一个候选值:终点的 − 该边权重。
  4. 。

为什么取 min(死线倒逼): 后面接了好几条任务,每条任务都对 的完成时刻有一个”最晚不能超过几号”的要求。哪条任务的要求最紧(最早到期), 就必须满足哪条。取最小值,是因为要迁就最紧的那个。

2.3 一句话铁律

算 ve 只看入边,算 vl 只看出边;不管这个点在不在关键路径上,也不管它离主干线多远,只要图上画了一条边通向它/从它发出,这条边就必须被算进去。


三、顶点 6 的坑:ve(6) 到底是 3 还是 6?

这题之前反复算错,原因就是没有把”入边清单”摆全。

先看原图,把指向顶点 6 的边找全:

  • ← 这条边很容易被漏看或漏算,是分歧的根源

只要原图上确实画了 ()这条边,那么按第二节的铁律,算 就必须把这条边也纳入候选:

如果漏看了 这条边,只用 一条边去算,就会错误地得到 。

通用排查方法:以后再遇到”这个点到底该算几”的分歧,不要靠回忆或直觉,而是:

  1. 圈出这个顶点;
  2. 把纸上/图上所有箭头指向它的边,用手指一条条点过去数一遍;
  3. 每条边都单独算一次候选值,最后统一取 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
32
4;;
2;;
6;;
7;;
5(汇点);;;;

→ 工程最短工期 = 12。

4.2 反向算 vl(逆拓扑序:5 → 2、7 → 4、6 → 3 → 1)

顶点出边清单(全部列出)候选值
5(汇点)——12(= 工期)
79
210
68
4;;;;;;
3;;
1(源点);;;;

五、事件(顶点)时间参数总表

事件是否关键事件()原图标注
100是单数 0
322是单数 2
455是单数 5
668否双数 [6 / 8]
2910否双数 [9 / 10]
799是单数 9
51212是单数 12

顶点标注规范:关键事件()只写一个数字;非关键事件写 [ve / vl]。


六、活动(边)时间参数总表

余量公式:

活动弧关键活动?
a1→3202−2=00✅
b1→25010−5=55
c3→6128−1=75
d1→4305−3=22
e3→4325−3=20✅
f4→24510−4=61
g4→6158−1=72
h6→7169−1=82
j4→51512−1=116(全场最大)
k2→52912−2=101
m4→7459−4=50✅
n7→53912−3=90✅

注意一个额外的坑:两个端点都是关键事件的边,不一定就是关键活动,还是要老老实实算一遍 是否为 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(汇点) = 工程总工期。