Appearance
关键路径（AOE 网）
为什么需要关键路径
工程项目中，有些活动可以并行，有些必须串行。关键路径就是从源点到汇点的最长路径——它决定了整个工程的最短完成时间。关键路径上的活动一旦延期，整个工程就延期。
408 考研中，关键路径属于图的应用章节，通常以选择题或应用题的形式出现，要求手动计算各事件/活动的时间参数并找出关键路径。
核心思想
关键路径的核心要素：
- AOE 网（Activity On Edge）：用有向无环图表示工程，顶点表示事件（Event），有向边表示活动（Activity），边的权值表示活动持续时间
- 关键路径 = 从源点到汇点的最长路径：路径长度等于各边权值之和，最长路径决定工程最短工期
- 关键活动：最早开始时间 e(i) 等于最晚开始时间 l(i) 的活动，即时间余量为 0 的活动
求解思路：先用拓扑排序求事件的最早发生时间 ve[]，再用逆拓扑排序求事件的最晚发生时间 vl[]，最后由 ve[] 和 vl[] 推导每条活动的 e[] 和 l[]。
交互可视化
通过下方的交互动画，你可以逐步观察关键路径的执行过程：
操作详解
基本概念
四个核心时间参数：
| 符号 | 含义 | 计算方式 |
|---|---|---|
| ve(j) | 事件 j 的最早发生时间 | ve(j) = max{ ve(i) + w(i,j) }，取所有前驱的最大值 |
| vl(j) | 事件 j 的最晚发生时间 | vl(j) = min{ vl(k) - w(j,k) }，取所有后继的最小值 |
| e(i) | 活动 aᵢ 的最早开始时间 | e(i) = ve(该活动的起点) |
| l(i) | 活动 aᵢ 的最晚开始时间 | l(i) = vl(该活动的终点) - w(aᵢ) |
关键概念辨析：
- 事件（顶点）：表示某些活动已完成、另一些活动可以开始的状态
- 活动（边）：表示实际需要耗费时间的子任务
- 源点：入度为 0 的顶点（工程开始），ve(源点) = 0
- 汇点：出度为 0 的顶点（工程结束），vl(汇点) = ve(汇点)
- 关键活动：满足 e(i) == l(i) 的活动，即 l(i) - e(i) == 0
求关键路径过程
关键步骤：
- 对 AOE 网进行拓扑排序，同时按拓扑序计算每个事件的 ve[]
- 按逆拓扑序计算每个事件的 vl[]（初始化 vl[汇点] = ve[汇点]）
- 遍历每条活动边，计算 e[] 和 l[]
- 找出所有 e(i) == l(i) 的活动，即为关键活动，关键活动构成关键路径
c
#include <stdio.h>
#include <string.h>
#define MAXV 1005
typedef struct {
int to, w, next;
} Edge;
Edge edges[MAXV * MAXV];
int head[MAXV], cnt;
int inDeg[MAXV];
int ve[MAXV], vl[MAXV]; // 事件最早/最晚发生时间
int topoOrder[MAXV], topoCnt; // 拓扑序列
int n, m; // n个事件, m个活动
void addEdge(int u, int v, int w) {
edges[cnt].to = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
inDeg[v]++;
}
// 拓扑排序 + 求 ve[]
int topoSort() {
int queue[MAXV], front = 0, rear = 0;
topoCnt = 0;
memset(ve, 0, sizeof(ve));
for (int i = 0; i < n; i++)
if (inDeg[i] == 0) queue[rear++] = i;
while (front < rear) {
int u = queue[front++];
topoOrder[topoCnt++] = u; // 记录拓扑序
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to, w = edges[i].w;
if (ve[u] + w > ve[v])
ve[v] = ve[u] + w; // 取最大值
if (--inDeg[v] == 0)
queue[rear++] = v;
}
}
return topoCnt == n; // 判断是否有环
}
// 求关键路径
void criticalPath() {
if (!topoSort()) return; // 有环则无关键路径
// 初始化 vl[] 为汇点的 ve 值
int maxVe = 0;
for (int i = 0; i < n; i++)
if (ve[i] > maxVe) maxVe = ve[i];
for (int i = 0; i < n; i++)
vl[i] = maxVe;
// 逆拓扑序求 vl[]
for (int idx = topoCnt - 1; idx >= 0; idx--) {
int u = topoOrder[idx];
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to, w = edges[i].w;
if (vl[v] - w < vl[u])
vl[u] = vl[v] - w; // 取最小值
}
}
// 遍历每条活动，判断是否为关键活动
for (int u = 0; u < n; u++) {
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to, w = edges[i].w;
int e = ve[u]; // 活动最早开始时间
int l = vl[v] - w; // 活动最晚开始时间
if (e == l) {
// <u, v> 是关键活动
}
}
}
}完整手算示例（建议跟着算一遍）
408 应用题给一个 AOE 网，要求填全 ve / vl / e / l 四张表再找关键路径。下面用一个 7 事件、10 活动的网走完全程——这是本章大题的标准动作，每一步都不能跳。
第一步：按拓扑序算 ve[]（正推取 max）
拓扑序：v1, v2, v3, v4, v5, v6, v7。每个事件对所有前驱取最大：
| 事件 | 计算过程 | ve |
|---|---|---|
| v1 | 源点 | 0 |
| v2 | ve(1) + 4 = 4 | 4 |
| v3 | ve(1) + 2 = 2 | 2 |
| v4 | max{ ve(2)+2, ve(3)+4 } = max | 6 |
| v5 | max{ ve(2)+3, ve(4)+2 } = max | 8 |
| v6 | max{ ve(3)+3, ve(4)+3 } = max | 9 |
| v7 | max{ ve(5)+1, ve(6)+4 } = max | 13 |
工程最短工期 = ve(汇点) = 13。
第二步：按逆拓扑序算 vl[]（倒推取 min）
初始化 vl(7) = ve(7) = 13。每个事件对所有后继取最小：
| 事件 | 计算过程 | vl |
|---|---|---|
| v7 | 汇点，= ve(7) | 13 |
| v6 | vl(7) − 4 = 9 | 9 |
| v5 | vl(7) − 1 = 12 | 12 |
| v4 | min{ vl(5)−2, vl(6)−3 } = min | 6 |
| v3 | min{ vl(4)−4, vl(6)−3 } = min | 2 |
| v2 | min{ vl(4)−2, vl(5)−3 } = min | 4 |
| v1 | min{ vl(2)−4, vl(3)−2 } = min | 0 |
自检习惯：算完必看 vl(源点) 是否等于 0。不等于 0 说明 ve 或 vl 某一步算错了，当场重查，别带着错往下填活动表。
第三步：逐活动算 e、l、d（活动表）
e(活动) = ve(起点)，l(活动) = vl(终点) − w，d = l − e：
| 活动 | 边 | w | e = ve(起) | l = vl(终) − w | 余量 d | 关键活动？ |
|---|---|---|---|---|---|---|
| a1 | v1→v2 | 4 | 0 | 4−4 = 0 | 0 | ★ |
| a2 | v1→v3 | 2 | 0 | 2−2 = 0 | 0 | ★ |
| a3 | v2→v4 | 2 | 4 | 6−2 = 4 | 0 | ★ |
| a4 | v2→v5 | 3 | 4 | 12−3 = 9 | 5 | |
| a5 | v3→v4 | 4 | 2 | 6−4 = 2 | 0 | ★ |
| a6 | v3→v6 | 3 | 2 | 9−3 = 6 | 4 | |
| a7 | v4→v5 | 2 | 6 | 12−2 = 10 | 4 | |
| a8 | v4→v6 | 3 | 6 | 9−3 = 6 | 0 | ★ |
| a9 | v5→v7 | 1 | 8 | 12−1 = 11 | 3 | |
| a10 | v6→v7 | 4 | 9 | 13−4 = 9 | 0 | ★ |
第四步：连出关键路径
关键活动 a1, a2, a3, a5, a8, a10 连成了两条关键路径：
- v1 → v2 → v4 → v6 → v7（4 + 2 + 3 + 4 = 13）
- v1 → v3 → v4 → v6 → v7（2 + 4 + 3 + 4 = 13）
第五步（命题人最爱的追问）：缩短哪个活动能缩短工期？
- 缩短 a1（只在第一条路径上）没用——第二条路径仍是 13，工期不变
- 缩短 a8 或 a10（两条关键路径的公共活动）有效——两条路径同时变短
- 即便缩短公共活动，也不能无限缩：a8 从 3 缩到一定程度后，原本余量大的路径（如 v1→v3→v6→v7 = 9）可能反超成为新的关键路径
这个例子里"v4 的两个前驱算出来同为 6"不是巧合，是特意设计的——ve 取 max 时出现并列就预示着多条关键路径，做题时看到并列要打起精神。
时间余量分析
活动 aᵢ 的时间余量 d(i) = l(i) - e(i)，表示该活动在不影响工期的前提下可以推迟的最大时间。
- d(i) == 0：关键活动，不能推迟，否则整个工期延长
- d(i) > 0：非关键活动，可以在 d(i) 范围内推迟开始或延长工期
注意事项：
- 关键路径可能不唯一，所有关键活动构成的路径都是关键路径
- 缩短工期只能通过缩短关键活动的持续时间来实现
- 缩短某关键活动后，该路径可能不再是关键路径（其他路径变为最长），需要重新计算
- 只有缩短所有关键路径上公共的关键活动，才能确保工期缩短
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 拓扑排序求 ve[] | O(V + E) | 遍历所有顶点和边各一次 |
| 逆拓扑序求 vl[] | O(V + E) | 遍历所有顶点和边各一次 |
| 求 e[] 和 l[] | O(E) | 遍历所有活动边 |
| 总体 | O(V + E) | 与拓扑排序同阶 |
空间复杂度：O(V + E)，需要存储图结构、ve[]、vl[] 及辅助栈/队列。
考研高频考点
- 手算 ve[]、vl[]、e[]、l[] 四组时间参数（应用题高频，建议熟悉）
- 根据 e(i) == l(i) 判断关键活动、找出关键路径（选择题/应用题高频考查）
- 关键路径与工程最短工期的关系（工期 = 关键路径长度 = ve[汇点]）
- AOE 网 vs AOV 网的区别（AOV 用顶点表示活动，AOE 用边表示活动）
- 关键路径不唯一时，缩短工期的条件分析（需缩短所有关键路径的公共关键活动）
- 关键路径算法与拓扑排序的关系（关键路径以拓扑排序为基础）
易错：关键路径是最长路径，不是最短路径——这和最短路径问题的思路恰好相反。关键路径上的活动时间余量为 0（最早开始时间 = 最晚开始时间）。
易错：关键路径可能不唯一。缩短工期必须同时缩短所有关键路径上的关键活动。如果只缩短一条关键路径上的活动，另一条关键路径可能变成新的瓶颈。
相关知识
- 拓扑排序：关键路径的计算以拓扑排序为基础
- BFS 遍历：拓扑排序的 BFS 实现（Kahn 算法）
- Dijkstra 算法：最短路径 vs 最长路径的对比，理解两者的本质区别