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> 是关键活动
}
}
}
}时间余量分析
活动 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 最长路径的对比，理解两者的本质区别