🏷️ 知识点：关键路径

下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是（ ）。

关键路径

A. 3 和 7 B. 12 和 12 C. 12 和 14 D. 15 和 15

[tag_link]

正确答案：C

AOE 网 是以边表示活动的有向无环网。活动 d 的弧尾事件必须等待所有前驱活动完成，其最早时间为 max{a, b+c}=max{3,4+8}=12。工程工期（源点到汇点的最长路径）为 27；由汇点逆推，d 的弧头事件最迟发生时间为 27-g=27-6=21，所以活动 d 最迟开始时间为 21-d=21-7=14。因此最早/最迟开始时间为 12 和 14，选 C。

下图是一个有 10 个活动的 AOE 网，时间余量最大的活动是（ ）。

A. c B. g C. h D. j

[tag_link]

正确答案：B

对活动 i→j，时间余量为 vl(j)-ve(i)-w(i,j)，其中 ve、vl 分别是事件最早发生时间和事件最迟发生时间。由图正推、反推可得 ve=(0,2,5,8,9,12)、vl=(0,4,5,8,11,12)。四个候选活动的余量为：c: 5-2-1=2，g: 12-5-1=6，h: 11-8-1=2，j: 12-9-1=2。最大的是活动 g，选 B。

下列关于 AOE 网的叙述中，正确的是（ ）。

A. 关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短 B. 关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少 C. 关键路径上任一关键活动改变后，都必然会影响关键路径的改变 D. 若所有的关键路径一同延长或缩短，则不会引起关键路径的改变

关键路径

[tag_link]

正确答案：B

AOE 网中关键路径是从源点到汇点的最长路径，决定了整个工程的最短完成时间。 选项 A 错误，因为缩短关键路径上某个活动的时间后，如果该活动不再是关键路径的一部分（例如其他路径成为新的关键路径），整个工程时间可能不变甚至增加。 选项 B 错误，因为延长关键路径上活动的时间可能使关键路径发生改变，从而工程延长时间不一定等于活动延长时间。 选项 C 错误，因为改变关键路径上的活动（如时间调整）不一定导致关键路径改变，例如缩短活动后原路径仍为最长时，关键路径不变。 选项 D 正确，当所有关键路径同时延长或缩短相同量时，这些路径的相对长度保持不变，没有其他路径成为更长路径，因此关键路径集合不会改变。

若使用 AOE 网估算工程进度，则下列叙述中正确的是（ ）。

关键路径

A. 关键路径是从源点到汇点边数最多的一条路径 B. 关键路径是从源点到汇点路径长度最长的路径 C. 增加任一关键活动的时间不会延长工程的工期 D. 缩短任一关键活动的时间将会缩短工程的工期

[tag_link]

正确答案：B

关键路径是从源点到汇点的最长路径，这里的“最长”指活动持续时间之和最大，而不是边数最多，所以 A 错、B 对。增加任一关键活动的持续时间，会使包含它的原关键路径超过原工期，因此 C 错。若有多条关键路径，缩短只属于其中一条路径的关键活动后，其他关键路径仍可能决定原工期，所以 D 也不一定成立。

下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）

关键路径

A.c 和 e

B.d 和 e

C.f 和 d

D.f 和 h

[tag_link] 正确答案：C找出 AOE 网的全部 关键路径 为 (b,d,c,g)、(b,d,e,h) 和 (b,f,h)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条：(b,d,cg)、(b,d,e,h) 和 (b,f,h)。由此可知，选项 A 和 B 中并不能包含 (b,f,h) 这条路径，选项 C 中，并不能包含 (b,d,c,g) 和 (b,d,e,h) 这两条路径，只有 C 包含了所有的关键路径，因此只有加快 f 和 d 的进度才能缩短工期。

已知有 6 个顶点（顶点编号为 0～5）的有向带权图 G ，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

(1) 写出图 G 的邻接矩阵 A 。

(2) 画出有向带权图 G 。

(3) 求图 G 的关键路径，并计算该关键路径的长度。

邻接矩阵 关键路径

[tag_link]

1）上三角矩阵 A[6][6] 中，第 1 行至第 5 行主对角线上方的元素个数分别为 5, 4, 3, 2, 1,由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。用“平移”的思想，将前 5 个、后 4 个、后 3 个、后 2 个、后 1 个元素，分别移动到矩阵对角线 (“0”) 右边的行上。图 G 的邻接矩阵 A 如下所示。

2）据上面的邻接矩阵，画出有向带权图 G, 如下图所示。

(3) 按照算法，先计算各个事件的最早发生时间，计算过程如下：ve(0)=0;ve(1)=ve(0)+a0→1=4;ve(

2)=max(ve(0)+a0→1,ve(

1)+a1→2)=max(6,4+

5)=9;ve(

3)=ve(

2)+a2→3=9+4=13;ve(

4)=ve(

2)+a2→4=9+3=12;ve(

5)=max(ve(

3)+a3→5,ve(

4)+a4→5)=max(16,1

5)=16;接下来求各个时间的最迟发生时间，计算过程如下：vl(

5)=ve(

5)=16;vl(

4)=vl(

5)−a4→5=16−3=13;vl(

3)=vl(

5)−a3→5=16−3=13;vl(

2)=min(vl(

3)−a2→3,vl(

4)−a2→4)=min(9,10)=9;vl(

1)=vl(

2)−a1→2=4;vl(0)=min(vl(

2)−a0→2,vl(

1)−a0→1)=min(3,0)=0;即 ve() 和 vl() 数组如下表所示。

接下来计算所有活动的最早和最迟发生时间 e() 和 l()：e(a0→1)=e(a0→2)=ve(0)=0;e(a1→2)=ve(1)=4;e(a2→3)=e(a2→4)=ve(2)=9;e(a3→5)=ve(3)=13;e(a4→5)=ve(4)=12;l(a4→5)=vl(5)−a4→5=16−3=13;l(a3→5)=vl(5)−a3→5=16−3=13;l(a2→4)=vl(4)−a2→4=13−3=10;l(a2→3)=vl(3)−a2→3=13−4=9;l(a1→2)=vl(2)−a1→2=9−5=4;l(a0→2)=vl(2)−a0→2=9−6=3;l(a0→1)=vl(1)−a0→1=4−4=0;e() 和 l() 数组与它们的差值如下表所示。

满足 l() - e() = 0 的路径就是关键路径，所以关键路径为a0→1、a1→2、a2→3、a3→5，如下图所示（粗线表示），长度为4+5+4+3=16。

AOE 网，描述 12 个工程活动及持续时间

(1) 完成该工程的最短时间是多少？哪些是关键活动？

(2) 若以最短时间完成工程，则与活动 e 同时进行的活动可能有哪些？

(3) 时间余量最大的活动是哪个？其时间余量是多少？

(4) 假设工程从时刻 0 启动，因某种原因，活动 b 在时刻 6 开始，为保证工程不延期，在其它活动持续时间保持不变的情况下，b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？

关键路径

[tag_link]

1）首先计算最早发生时间 ve：

然后计算最晚发生时间：

ve 和 vl 相同的顶点为 1、3、4、7、5，所以关键活动为 a、e、m、n。

2）e 的执行时间是 2~5，可以与 e 同时执行的活动为 b、d、c。

3）假设有顶点 i→j 的活动（边），则该活动的 时间余量 = vl(j) - ve(i) - 边的长度。计算所有非关键路径上活动的时间余量，可以得到活动 j 的时间余量是最大的，为 vl(5) - ve(4) - 1 = 6。

4）为保证 1 → 2 → 5 的路径长度不超过关键路径的长度，需要保证 6 + b + k ≤ 12，所以 b ≤ 4，即 b 的持续时间最长为 4。如果想要保证 b 仍然为 5 的话，需要压缩 k 的时间长度，将 k 缩小为 1。

下面关于求关键路径的说法中，不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的 B. 一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同 C. 一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差 D. 任何一个活动的持续时间的改变可能会影响关键路径的改变

正确答案：C

结论

选 C。对弧 i→j，i 确实是弧尾；事件 i 的最迟发生时间应等于所有出边活动最迟开始时间的最小值，即 vl(i)=min(vl(j)-d(i,j))。选项 C 把活动最迟开始时间又减了一次持续时间，造成多减一次 d。

推导

按拓扑序计算 ve，再按逆拓扑序计算 vl，活动的时间余量为 vl(j)-ve(i)-d(i,j)。对每条出边 i→j，活动最迟开始时间是 vl(j)-d(i,j)；事件 i 的最迟发生时间就是这些出边活动最迟开始时间的最小值，不能再减一次 d(i,j)。详见 AOE 递推。

易错点

不要把“事件最迟发生”与“某一条出边活动的最迟开始”混为一谈；有多条出边时必须对 vl(j)-d(i,j) 取最小值，也不要把持续时间多减一次。改变任一活动持续时间也可能改变 ve、vl 或关键路径集合。

下列关于AOE网的关键路径的说法中，正确的是（ ）。

Ⅰ．改变网上某一关键路径上的任意一个关键活动后，必将产生不同的关键路径 Ⅱ．关键路径上活动的时间延长多少，整个工期也就随之延长多少 Ⅲ．缩短关键路径上任意一个关键活动的持续时间可缩短关键路径长度 Ⅳ．缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度 Ⅴ．缩短多条关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度

A. Ⅱ和Ⅴ B. Ⅰ、Ⅱ和Ⅳ C. Ⅱ和Ⅳ D. Ⅰ和Ⅳ

正确答案：C

结论

选 C，Ⅱ和Ⅳ正确。关键路径上的活动延长会等量推迟工期；要缩短工期，必须缩短所有当前关键路径共有的活动。

推导

活动松弛量为 vl(j)-ve(i)-d(i,j)，为零的活动才是关键活动。缩短只出现在一条关键路径上的活动，另一条同长路径仍会控制工期；只有覆盖全部关键路径的公共关键活动缩短，最长路径才会下降。详见 关键路径缩短条件。

易错点

“任意关键活动”不等于“所有关键路径共有的关键活动”。缩短后还需重新计算关键路径，原路径可能不再唯一；Ⅰ、Ⅲ、Ⅴ的表述都把必要条件说成了充分条件。

在求 AOE网的关键路径时，若该有向图用邻接矩阵表示且第i 列值全为∞，则（ ）。

A. 若关键路径存在，第i 个顶点一定是起点 B. 若关键路径存在，第i 个顶点一定是终点 C. 关键路径不存在 D. 该有向图对应的无向图存在多个连通分量

正确答案：A

结论

选 A。在矩阵约定 a[u][v] 表示 u→v 时，第 i 列全为 ∞ 表示没有入边，即顶点 i 入度为零；在 AOE 网存在关键路径且源点唯一的前提下，它就是起点。

推导

邻接矩阵的列统计入边、行统计出边。入度为零的顶点只能作为工程源点候选；“关键路径存在”以及 AOE 网通常要求唯一源点，才可判定为起点。详见 邻接矩阵列与入度。

易错点

列全 ∞ 只说明无入边，不说明终点（终点应看出度为零，即行全 ∞），也不能单独推出图不连通；必须结合 AOE 网的单一源点和关键路径存在前提。

下表给出了某工程各工序之间的优先关系和各工序所需的时间(其中“一”表示无先 驱工序),请完成以下各题： 1)画出相应的AOE网 。 2)列出各事件的最早发生时间和最迟发生时间。 3)求出关键路径并指明完成该工程所需的最短时间。 工序代号 A B C D E F G H 所需时间 3 2 2 3 4 3 2 1

先驱工序 一 一 A A B A C、E D

[tag_link]

参考答案

可把工序表转换为下面的 AOE 边集；顶点编号只是为了表达依赖关系，虚活动可按等价方式设置。

按拓扑序正向计算事件最早发生时间，按逆拓扑序反向计算最迟发生时间：

对活动 i→j，最早开始 e=ve(i)，最迟开始 l=vl(j)-duration，时差为 l-e：

因此关键活动为 B、E、G，关键路径是 1→3→4→8，最短工期为 8 个时间单位。

易错点

活动 F 虽然直接通向汇点，但路径 1→2→8 只有 6，不决定总工期；关键活动必须满足时差为 0，不能只看是否连接汇点。