408

数据结构

关键路径

---

一、定位信息

• 圈层：核心层（大纲考点）
• 前置知识：有向图的基本概念、图的存储（邻接表/邻接矩阵）、拓扑排序（DS-05-06）、AOV 网与 AOE 网的概念。
• 知识网络定位：关键路径是 AOE 网（Activity On Edge Network）分析的核心问题，建立在拓扑排序的基础之上。它通过求解事件的最早/最晚发生时间来确定工程的最短工期和关键活动，是图论在工程管理中的经典应用。
• 考点热度：H级（高频重点） — 近 5 年真题中出现 ≥3 次，手算关键路径过程（求 $ve, vl, e, l$）是高频考点，单次分值 5–10 分。

---

二、知识点讲解

2.1 AOE 网的定义

AOE 网（Activity On Edge Network）：用边（弧）表示活动、用顶点表示事件的带权有向无环图（DAG）。边上的权值表示活动的持续时间（工期）。

• 源点：入度为 0 的顶点，表示整个工程的开始。
• 汇点：出度为 0 的顶点，表示整个工程的结束。
• 事件 $v_i$：表示所有以 $v_i$ 为弧头的活动已经完成、所有以 $v_i$ 为弧尾的活动可以开始的状态。

直观理解：把一个大工程拆成若干活动（边），活动之间有先后顺序（顶点表示阶段性节点）。每条边上标注该活动需要的时间。关键路径就是决定整个工程最短工期的那条"最要命"的路径。

2.2 四个核心变量

变量	含义	计算方向
$ve(i)$ — 事件最早发生时间	事件 $v_i$ 最早可以在什么时刻发生	从源点出发，正向递推
$vl(i)$ — 事件最晚发生时间	事件 $v_i$ 最晚必须在什么时刻发生（否则会延误工期）	从汇点出发，逆向递推
$e(k)$ — 活动最早开始时间	活动 $a_k$（弧 $\langle v_i, v_j \rangle$）最早可以开始的时刻	$e(k) = ve(i)$
$l(k)$ — 活动最晚开始时间	活动 $a_k$ 最晚必须开始的时刻（否则会延误工期）	$l(k) = vl(j) - \text{dut}(a_k)$

2.3 计算公式

事件最早发生时间 $ve$（正向递推，从源点到汇点）：

$ve(j) = \max_{\langle v_i, v_j \rangle \in E} \{ve(i) + \text{dut}(\langle v_i, v_j \rangle)\}$

含义：事件 $v_j$ 的最早发生时间 = 所有前驱事件的最早时间加上对应活动的持续时间，取最大值。因为所有前驱活动都完成后，事件才能发生。

事件最晚发生时间 $vl$（逆向递推，从汇点到源点）：

$vl(i) = \min_{\langle v_i, v_j \rangle \in E} \{vl(j) - \text{dut}(\langle v_i, v_j \rangle)\}$

含义：事件 $v_i$ 的最晚发生时间 = 所有后继事件的最晚时间减去对应活动的持续时间，取最小值。因为必须给后续活动留出足够时间。

关键活动：满足 $e(k) = l(k)$ 的活动。关键活动没有余量（松弛时间为 0），任何延误都会导致整个工程延期。

关键路径：从源点到汇点的、由所有关键活动组成的路径。关键路径的长度（权值之和）= 工程的最短工期。

2.4 算法步骤

1. 对 AOE 网进行拓扑排序，得到顶点的拓扑有序序列（用于正向递推 $ve$）。
2. 正向递推求 $ve$：按拓扑序列顺序，对每个顶点用公式 $ve(j) = \max\{ve(i) + dut\}$ 计算。
3. 逆向递推求 $vl$：按拓扑序列的逆序，对每个顶点用公式 $vl(i) = \min\{vl(j) - dut\}$ 计算。
4. 求每条弧的 $e$ 和 $l$：对弧 $\langle v_i, v_j \rangle$，$e = ve(i)$，$l = vl(j) - dut$。
5. 找关键活动：$e(k) = l(k)$ 的活动即为关键活动。
6. 确定关键路径：由关键活动连接而成的从源点到汇点的路径。

伪代码：

bool CriticalPath(ALGraph G) {
    // 求 AOE 网的关键路径
    int ve[MAX_VERTEX_NUM];   // 事件最早发生时间
    int vl[MAX_VERTEX_NUM];   // 事件最晚发生时间
    int topo[MAX_VERTEX_NUM]; // 拓扑序列
    
    // Step 1: 拓扑排序，同时正向求 ve
    if (!TopologicalSort(G, topo))  // 拓扑排序失败，有环
        return false;
    
    // 初始化所有事件的最早发生时间为 0
    for (int i = 0; i < G.vexnum; i++)
        ve[i] = 0;
    
    // Step 2: 正向递推 ve（按拓扑序列顺序）
    for (int i = 0; i < G.vexnum; i++) {
        int v = topo[i];              // 取拓扑序列中的第 i 个顶点
        ArcNode *p = G.vertices[v].firstarc;
        while (p) {
            int w = p->adjvex;        // w 是 v 的后继
            if (ve[v] + p->weight > ve[w])
                ve[w] = ve[v] + p->weight;  // 取最大值
            p = p->nextarc;
        }
    }
    
    // Step 3: 逆向递推 vl（按拓扑序列逆序）
    int maxlen = ve[topo[G.vexnum - 1]]; // 汇点的 ve 即为工程最短工期
    for (int i = 0; i < G.vexnum; i++)
        vl[i] = maxlen;              // 初始化为汇点的 ve
    
    for (int i = G.vexnum - 1; i >= 0; i--) {
        int v = topo[i];              // 逆序取顶点
        ArcNode *p = G.vertices[v].firstarc;
        while (p) {
            int w = p->adjvex;
            if (vl[w] - p->weight < vl[v])
                vl[v] = vl[w] - p->weight;  // 取最小值
            p = p->nextarc;
        }
    }
    
    // Step 4: 求每条弧的 e 和 l，找关键活动
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].firstarc;
        while (p) {
            int j = p->adjvex;
            int e = ve[i];            // 活动最早开始 = 弧尾事件的 ve
            int l = vl[j] - p->weight; // 活动最晚开始 = 弧头事件的 vl - 活动持续时间
            if (e == l)               // e == l，关键活动
                printf("关键活动：<v%d, v%d>，权值=%d\n", i, j, p->weight);
            p = p->nextarc;
        }
    }
    return true;
}

时间复杂度：$O(n + e)$（拓扑排序 $O(n+e)$，正向递推 $O(n+e)$，逆向递推 $O(n+e)$，求 $e/l$ 遍历所有弧 $O(e)$）。

2.5 完整执行示例

示例 AOE 网：

【图示说明】AOE 网有 6 个事件（顶点）$v_0 \sim v_5$，其中 $v_0$ 为源点，$v_5$ 为汇点。活动（弧）及持续时间：$a_1: \langle v_0,v_1 \rangle, dur=3$；$a_2: \langle v_0,v_2 \rangle, dur=4$；$a_3: \langle v_1,v_3 \rangle, dur=5$；$a_4: \langle v_2,v_3 \rangle, dur=2$；$a_5: \langle v_2,v_4 \rangle, dur=7$；$a_6: \langle v_3,v_5 \rangle, dur=6$；$a_7: \langle v_4,v_5 \rangle, dur=4$。

Step 1：拓扑排序 拓扑序列：$v_0, v_1, v_2, v_3, v_4, v_5$

Step 2：正向递推求 $ve$

顶点	计算过程	$ve$
$v_0$	源点	0
$v_1$	$ve(v_0) + 3 = 3$	3
$v_2$	$ve(v_0) + 4 = 4$	4
$v_3$	$\max(ve(v_1)+5, ve(v_2)+2) = \max(8, 6) = 8$	8
$v_4$	$ve(v_2) + 7 = 11$	11
$v_5$	$\max(ve(v_3)+6, ve(v_4)+4) = \max(14, 15) = 15$	15

工程最短工期 = $ve(v_5) = 15$。

Step 3：逆向递推求 $vl$

顶点	计算过程	$vl$
$v_5$	汇点，$vl = ve = 15$	15
$v_4$	$vl(v_5) - 4 = 11$	11
$v_3$	$vl(v_5) - 6 = 9$	9
$v_2$	$\min(vl(v_3)-2, vl(v_4)-7) = \min(7, 4) = 4$	4
$v_1$	$vl(v_3) - 5 = 4$	4
$v_0$	$\min(vl(v_1)-3, vl(v_2)-4) = \min(1, 0) = 0$	0

Step 4：求每条弧的 $e$ 和 $l$

活动	弧	持续时间	$e = ve(i)$	$l = vl(j) - dur$	$l - e$	关键？
$a_1$	$\langle v_0,v_1 \rangle$	3	0	$4-3=1$	1	否
$a_2$	$\langle v_0,v_2 \rangle$	4	0	$4-4=0$	0	是
$a_3$	$\langle v_1,v_3 \rangle$	5	3	$9-5=4$	1	否
$a_4$	$\langle v_2,v_3 \rangle$	2	4	$9-2=7$	3	否
$a_5$	$\langle v_2,v_4 \rangle$	7	4	$11-7=4$	0	是
$a_6$	$\langle v_3,v_5 \rangle$	6	8	$15-6=9$	1	否
$a_7$	$\langle v_4,v_5 \rangle$	4	11	$15-4=11$	0	是

Step 5：关键路径

关键活动：$a_2, a_5, a_7$

关键路径：$v_0 \xrightarrow{a_2} v_2 \xrightarrow{a_5} v_4 \xrightarrow{a_7} v_5$

路径长度：$4 + 7 + 4 = 15$ = 工程最短工期。✓

---

三、记忆与理解辅助

技巧 1：关键路径四步口诀

"拓扑排序打基础，正向 $ve$ 取最大，逆向 $vl$ 取最小，$e=l$ 就是关键活动"

技巧 2：$ve$ 与 $vl$ 的直觉理解

变量	方向	取 max/min	直觉
$ve$（最早）	源点→汇点	$\max$	所有前驱都完成了才能开始，所以取最大的
$vl$（最晚）	汇点→源点	$\min$	必须给后续留够时间，所以取最小的

技巧 3：关键活动的物理意义

• $e(k) = l(k)$：该活动没有任何缓冲时间，必须按时开始，否则整个工程延期。
• $l(k) - e(k) > 0$：该活动有 $l(k) - e(k)$ 个单位时间的余量（松弛时间），可以适当延迟而不影响工期。

技巧 4：$ve$ 与 $vl$ 计算对比表

对比维度	$ve$（最早发生时间）	$vl$（最晚发生时间）
计算方向	从源点到汇点（正向）	从汇点到源点（逆向）
遍历顺序	拓扑序列顺序	拓扑序列逆序
聚合方式	$\max$（所有前驱取最大）	$\min$（所有后继取最小）
初始化	源点 $ve = 0$	汇点 $vl = ve(\text{汇点})$
依赖关系	依赖前驱的 $ve$	依赖后继的 $vl$

技巧 5：关键路径不唯一

• 一个 AOE 网可能有多条关键路径（不同的路径长度相同且都等于最短工期）。
• 但所有关键路径上的活动都是关键活动。
• 要缩短工期，必须同时缩短所有关键路径上的至少一个活动。

---

四、例题与精解

例题 1（基础巩固 — 手算关键路径）

题目：对下图所示的 AOE 网，求所有事件的 $ve$ 和 $vl$，找出关键活动和关键路径，确定工程最短工期。

【图示说明】AOE 网有 4 个事件 $v_0, v_1, v_2, v_3$，其中 $v_0$ 为源点，$v_3$ 为汇点。活动：$a_1: \langle v_0,v_1 \rangle, dur=2$；$a_2: \langle v_0,v_2 \rangle, dur=3$；$a_3: \langle v_1,v_3 \rangle, dur=4$；$a_4: \langle v_2,v_3 \rangle, dur=2$。

命题意图：考查关键路径的完整计算过程，包括 $ve, vl, e, l$ 的求解。

审题分析：

• 已知：4 个事件、4 条活动的 AOE 网。
• 求解：$ve, vl$，关键活动，关键路径，最短工期。

解题思路：按关键路径算法，先拓扑排序，再正向求 $ve$、逆向求 $vl$，最后求 $e, l$。

完整步骤：

(1) 拓扑序列：$v_0, v_1, v_2, v_3$

(2) 正向求 $ve$：

顶点	计算	$ve$
$v_0$	源点	0
$v_1$	$ve(v_0) + 2 = 2$	2
$v_2$	$ve(v_0) + 3 = 3$	3
$v_3$	$\max(ve(v_1)+4, ve(v_2)+2) = \max(6, 5) = 6$	6

(3) 逆向求 $vl$：

顶点	计算	$vl$
$v_3$	汇点	6
$v_2$	$vl(v_3) - 2 = 4$	4
$v_1$	$vl(v_3) - 4 = 2$	2
$v_0$	$\min(vl(v_1)-2, vl(v_2)-3) = \min(0, 1) = 0$	0

(4) 求 $e$ 和 $l$：

活动	弧	dur	$e$	$l$	$l-e$	关键？
$a_1$	$\langle v_0,v_1 \rangle$	2	0	$2-2=0$	0	是
$a_2$	$\langle v_0,v_2 \rangle$	3	0	$4-3=1$	1	否
$a_3$	$\langle v_1,v_3 \rangle$	4	2	$6-4=2$	0	是
$a_4$	$\langle v_2,v_3 \rangle$	2	3	$6-2=4$	1	否

关键活动：$a_1, a_3$

关键路径：$v_0 \xrightarrow{a_1} v_1 \xrightarrow{a_3} v_3$

最短工期：$2 + 4 = 6$

方法反思：本题只有一条关键路径。$a_2$ 和 $a_4$ 各有 1 个单位时间的余量，适当延迟不影响工期。若要缩短工期，只需压缩 $a_1$ 或 $a_3$ 的持续时间。

---

例题 2（中等提升 — 综合分析与工期优化）

题目：某工程的 AOE 网如下，求关键路径和最短工期。若要将工期缩短 2 天，应优先压缩哪些活动？

【图示说明】AOE 网有 6 个事件 $v_0 \sim v_5$，$v_0$ 为源点，$v_5$ 为汇点。活动：$a_1: \langle v_0,v_1 \rangle, dur=5$；$a_2: \langle v_0,v_2 \rangle, dur=6$；$a_3: \langle v_1,v_3 \rangle, dur=3$；$a_4: \langle v_2,v_3 \rangle, dur=6$；$a_5: \langle v_2,v_4 \rangle, dur=4$；$a_6: \langle v_3,v_5 \rangle, dur=3$；$a_7: \langle v_4,v_5 \rangle, dur=4$。

命题意图：综合考查关键路径的完整求解过程，以及利用关键活动分析进行工期优化的能力。

审题分析：

• 已知：6 个事件、7 条活动的 AOE 网。
• 求解：关键路径、最短工期、工期优化方案。

解题思路：标准流程求关键路径，再根据关键活动的松弛时间确定优化方案。

完整步骤：

(1) 拓扑序列：$v_0, v_1, v_2, v_3, v_4, v_5$

(2) 正向求 $ve$：

顶点	计算	$ve$
$v_0$	源点	0
$v_1$	$0 + 5 = 5$	5
$v_2$	$0 + 6 = 6$	6
$v_3$	$\max(5+3, 6+6) = \max(8, 12) = 12$	12
$v_4$	$6 + 4 = 10$	10
$v_5$	$\max(12+3, 10+4) = \max(15, 14) = 15$	15

(3) 逆向求 $vl$：

顶点	计算	$vl$
$v_5$	汇点	15
$v_4$	$15 - 4 = 11$	11
$v_3$	$15 - 3 = 12$	12
$v_2$	$\min(12-6, 11-4) = \min(6, 7) = 6$	6
$v_1$	$12 - 3 = 9$	9
$v_0$	$\min(9-5, 6-6) = \min(4, 0) = 0$	0

(4) 求 $e$ 和 $l$：

活动	弧	dur	$e = ve(i)$	$l = vl(j) - dur$	$l - e$	关键？
$a_1$	$\langle v_0,v_1 \rangle$	5	0	$9-5=4$	4	否
$a_2$	$\langle v_0,v_2 \rangle$	6	0	$6-6=0$	0	是
$a_3$	$\langle v_1,v_3 \rangle$	3	5	$12-3=9$	4	否
$a_4$	$\langle v_2,v_3 \rangle$	6	6	$12-6=6$	0	是
$a_5$	$\langle v_2,v_4 \rangle$	4	6	$11-4=7$	1	否
$a_6$	$\langle v_3,v_5 \rangle$	3	12	$15-3=12$	0	是
$a_7$	$\langle v_4,v_5 \rangle$	4	10	$15-4=11$	1	否

关键活动：$a_2, a_4, a_6$

关键路径：$v_0 \xrightarrow{a_2} v_2 \xrightarrow{a_4} v_3 \xrightarrow{a_6} v_5$

最短工期：$6 + 6 + 3 = 15$

(5) 工期优化分析：

要缩短 2 天，必须压缩关键路径上的活动。优先选择压缩成本最低或持续时间最长的关键活动：

• $a_2$（dur=6）：压缩空间较大，优先考虑。
• $a_4$（dur=6）：同样有较大压缩空间。
• $a_6$（dur=3）：压缩空间较小。

注意：压缩关键活动后，需重新检查关键路径是否变化。若压缩 $a_2$ 后，$v_0 \to v_1 \to v_3 \to v_5$（路径长 $5+3+3=11$）成为新的关键路径，则需继续分析。

方法反思：关键路径决定了工程的最短工期。缩短工期必须从关键活动入手，但压缩后关键路径可能变化，需要重新计算。非关键活动（如 $a_1, a_3, a_5, a_7$）有余量，压缩它们不会缩短工期。

---

五、考情分析

• 考查频次：近 5 年真题中出现 ≥3 次，是图论部分的核心考点之一。
• 常见题型：选择题（判断关键活动、计算松弛时间）、综合应用题（手算关键路径全过程、代码填空）。
• 分值占比：选择题 2 分，综合题 5–10 分。
• 命题趋势：手算关键路径（求 $ve, vl, e, l$）是高频大题，常与拓扑排序结合考查。近年来增加了对"工期优化"和"关键路径不唯一"情况的分析考查。
• 基于大纲与命题规律推测

---

六、易错点提醒

1. 错误表现：正向求 $ve$ 时用 $\min$ 而非 $\max$。 错误原因：混淆了 $ve$ 和 $vl$ 的聚合方式。$ve$ 表示"最早"发生时间，必须所有前驱活动都完成才能发生，所以取最大值。 正确做法：$ve$ 正向递推取 $\max$，$vl$ 逆向递推取 $\min$。口诀："最早取大，最晚取小"。

2. 错误表现：逆向求 $vl$ 时未将所有顶点初始化为汇点的 $ve$ 值。 错误原因：$vl$ 的初始化应该是汇点的 $ve$（即工程最短工期），不是 0 或 $\infty$。如果初始化错误，会导致 $vl$ 计算结果偏差。 正确做法：先将所有 $vl[i]$ 初始化为 $ve(\text{汇点})$，再按拓扑逆序更新。

3. 错误表现：将 $e(k) = ve(i)$ 中的 $i$ 错误理解为弧头而非弧尾。 错误原因：活动 $a_k$ 对应弧 $\langle v_i, v_j \rangle$，活动的最早开始时间取决于弧尾（起点）事件的最早发生时间，即 $e(k) = ve(i)$。 正确做法：$e(k) = ve(\text{弧尾})$，$l(k) = vl(\text{弧头}) - dur$。

4. 错误表现：认为关键路径一定是权值之和最大的路径。 错误原因：虽然关键路径确实是源点到汇点的最长路径（决定了最短工期），但"最长路径"的判定需要通过 $ve, vl, e, l$ 的计算来确认，不能简单地通过肉眼找"看起来最长"的路径。 正确做法：严格按算法计算，$e(k) = l(k)$ 的活动才是关键活动，由关键活动组成的路径才是关键路径。

5. 错误表现：压缩工期时只压缩一条关键路径上的活动，忽略了其他关键路径。 错误原因：若存在多条关键路径，只压缩其中一条路径上的活动，其他关键路径不变，工期不会缩短。 正确做法：必须同时压缩所有关键路径上的至少一个活动，才能真正缩短工期。

---

七、来源标注

• 依据 2026 考研统考大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据大学本科经典教材共识