关键路径

概念

AOE 网（Activity on Edge Network）是用有向边表示活动、边上的权值表示活动持续时间、顶点表示事件（某个时刻的状态）的带权有向无环图。

• 源点（起点）：入度为 0，表示工程开始；
• 汇点（终点）：出度为 0，表示工程结束；
• 关键路径（Critical Path）：从源点到汇点的路径长度最长的那条路径；
• 关键活动：关键路径上的活动，即最早开始时间 = 最迟开始时间（时间余量为 0）的活动。

一句话理解：工程里所有前置活动都干完才能进入下一个事件，所以整个工程的最短完成时间 = 从开始到结束耗时最长的那条链。这条链上的活一天都不能拖——它就是关键路径。

注意这个"反直觉"的说法：关键路径是最长路径，但它对应的工期叫最短工期——因为它是"不可能更短的下界"。

原理

两组时间

（1）事件的时间

记号	含义	递推
$ve(k)$	事件 k 的最早发生时间	$ve(k)=\underset{⟨j,k⟩}{max}\{ve(j)+w(j,k)\}$
$vl(k)$	事件 k 的最迟发生时间	$vl(k)=\underset{⟨k,j⟩}{min}\{vl(j)-w(k,j)\}$

• 算 $ve$：按拓扑序从前往后，取 max（要等所有前置都完成）。
• 算 $vl$：按逆拓扑序从后往前，取 min（不能耽误任何后继）。
• 初始化：$ve(\mathrm{源}\mathrm{点})=0$；$vl(\mathrm{汇}\mathrm{点})=ve(\mathrm{汇}\mathrm{点})$（汇点不能拖）。

（2）活动的时间

对活动 $a=⟨i,j⟩$，持续时间为 $w$：

$$e(a)=ve(i)l(a)=vl(j)-w$$

• $e(a)$：活动 a 的最早开始时间（它的起点事件最早何时发生）；
• $l(a)$：活动 a 的最迟开始时间（倒推：终点事件最迟 $vl(j)$ 发生，减去自身耗时）；
• 时间余量 $d(a)=l(a)-e(a)$：可以"偷懒"的天数，不影响总工期。

关键活动 ⟺ $d(a)=0$，即 $e(a)=l(a)$，一点余量都没有。

算法骨架

1. 对 AOE 网做拓扑排序，得到拓扑序列（顺便判环，有环则工程无法完成）
2. 置 ve[] 全 0；按拓扑序求 ve：ve[k] = max(ve[k], ve[j] + w(j,k))
3. 置 vl[] 全为 ve[汇点]；按逆拓扑序求 vl：vl[k] = min(vl[k], vl[j] - w(k,j))
4. 对每条弧 <i,j,w>：e = ve[i]，l = vl[j] - w，若 e == l 则为关键活动
5. 所有关键活动构成的从源点到汇点的路径即关键路径（可能不止一条）

复杂度：拓扑排序 $O(n+e)$，求 ve、vl、活动表各 $O(n+e)$，总 $O(n+e)$（邻接表）或 $O(n^2)$（邻接矩阵）。

三个工程结论（常在选择题里出现）

1. 关键活动延期一天 → 总工期延期一天；非关键活动在其时间余量内延期不影响总工期。
2. 缩短总工期必须缩短关键活动，而且如果关键路径不止一条，必须同时缩短所有关键路径上的活动，否则只缩短其中一条没用。
3. 关键活动被压缩到一定程度后，关键路径可能发生变化（原本的非关键路径变成关键路径）。

示例

某工程的 AOE 网如下（顶点为事件 $v_1\sim v_9$，弧为活动 $a_1\sim a_{11}$）：

活动	弧	持续时间
$a_1$	$v_1\to v_2$	6
$a_2$	$v_1\to v_3$	4
$a_3$	$v_1\to v_4$	5
$a_4$	$v_2\to v_5$	1
$a_5$	$v_3\to v_5$	1
$a_6$	$v_4\to v_6$	2
$a_7$	$v_5\to v_7$	9
$a_8$	$v_5\to v_8$	7
$a_9$	$v_6\to v_8$	4
$a_{10}$	$v_7\to v_9$	2
$a_{11}$	$v_8\to v_9$	4

   ① ──a1(6)──► ② ──a4(1)──► ⑤ ──a7(9)──► ⑦ ──a10(2)──┐
   │                     ▲     │                        ▼
   │                     │     │                        ⑨
   ├─a2(4)──► ③ ─a5(1)───┘     │                        ▲
   │                           │                        │
   │                           └──a8(7)──► ⑧ ──a11(4)───┘
   │                                       ▲
   └─a3(5)──► ④ ──a6(2)──► ⑥ ──a9(4)───────┘

   源点 v1（入度 0）                          汇点 v9（出度 0）

第 1 步：拓扑排序

入度：$v_1$: 0，$v_2$: 1，$v_3$: 1，$v_4$: 1，$v_5$: 2，$v_6$: 1，$v_7$: 1，$v_8$: 2，$v_9$: 2

拓扑序列：v1, v2, v3, v4, v5, v6, v7, v8, v9   （长度 9 = n，无环 ✓）

第 2 步：求 $ve$（按拓扑序，取 max）

事件	计算公式	$ve$
$v_1$	源点，初始化	0
$v_2$	$ve(1)+6=0+6$	6
$v_3$	$ve(1)+4=0+4$	4
$v_4$	$ve(1)+5=0+5$	5
$v_5$	$max(ve(2)+1,ve(3)+1)=max(7,5)$	7
$v_6$	$ve(4)+2=5+2$	7
$v_7$	$ve(5)+9=7+9$	16
$v_8$	$max(ve(5)+7,ve(6)+4)=max(14,11)$	14
$v_9$	$max(ve(7)+2,ve(8)+4)=max(18,18)$	18

工程最短工期 = ve(v9) = 18

第 3 步：求 $vl$（按逆拓扑序，取 min）

先把 $vl(v_9)=ve(v_9)=18$，其余先置为 18。

事件（逆序）	计算公式	$vl$
$v_9$	汇点 = $ve(9)$	18
$v_8$	$vl(9)-4=18-4$	14
$v_7$	$vl(9)-2=18-2$	16
$v_6$	$vl(8)-4=14-4$	10
$v_5$	$min(vl(7)-9,vl(8)-7)=min(7,7)$	7
$v_4$	$vl(6)-2=10-2$	8
$v_3$	$vl(5)-1=7-1$	6
$v_2$	$vl(5)-1=7-1$	6
$v_1$	$min(vl(2)-6,vl(3)-4,vl(4)-5)=min(0,2,3)$	0

第 4 步：活动表与关键活动

活动	弧	$w$	$e=ve(i)$	$l=vl(j)-w$	$d=l-e$	关键？
$a_1$	$1\to 2$	6	0	$6-6=0$	0	✅ 关键
$a_2$	$1\to 3$	4	0	$6-4=2$	2
$a_3$	$1\to 4$	5	0	$8-5=3$	3
$a_4$	$2\to 5$	1	6	$7-1=6$	0	✅ 关键
$a_5$	$3\to 5$	1	4	$7-1=6$	2
$a_6$	$4\to 6$	2	5	$10-2=8$	3
$a_7$	$5\to 7$	9	7	$16-9=7$	0	✅ 关键
$a_8$	$5\to 8$	7	7	$14-7=7$	0	✅ 关键
$a_9$	$6\to 8$	4	7	$14-4=10$	3
$a_{10}$	$7\to 9$	2	16	$18-2=16$	0	✅ 关键
$a_{11}$	$8\to 9$	4	14	$18-4=14$	0	✅ 关键

关键活动：$a_1,a_4,a_7,a_8,a_{10},a_{11}$。

第 5 步：还原关键路径

从源点沿关键活动走出两条路径：

① ──a1(6)──► ② ──a4(1)──► ⑤ ──a7(9)──► ⑦ ──a10(2)──► ⑨     长度 = 6+1+9+2 = 18
① ──a1(6)──► ② ──a4(1)──► ⑤ ──a8(7)──► ⑧ ──a11(4)──► ⑨     长度 = 6+1+7+4 = 18

**关键路径有两条，长度都是 18。**这正是"想压缩工期必须同时动两条"的典型场景：若只把 $a_7$ 从 9 压到 7，第一条降到 16，但第二条仍是 18，总工期纹丝不动。

事件是否"关键"（$ve=vl$）：$v_1,v_2,v_5,v_7,v_8,v_9$ 关键；$v_3$（4 vs 6）、$v_4$（5 vs 8）、$v_6$（7 vs 10）非关键。

C 语言：完整求解

#include <stdio.h>

#define MAXV 20
#define MAXE 100

int n, e;
int g[MAXV][MAXV];            /* 邻接矩阵，g[i][j] = 活动 <i,j> 的持续时间，0 表示无弧 */
int indeg[MAXV], ve[MAXV], vl[MAXV], topo[MAXV], tcnt;

void topoSort(void) {
    int q[MAXV], f = 0, r = 0;
    for (int i = 1; i <= n; i++) if (indeg[i] == 0) q[r++] = i;
    while (f < r) {
        int u = q[f++];
        topo[tcnt++] = u;
        for (int v = 1; v <= n; v++)
            if (g[u][v] && --indeg[v] == 0) q[r++] = v;
    }
}

int main(void) {
    n = 9; e = 11;
    int A[MAXE][3] = { {1,2,6},{1,3,4},{1,4,5},{2,5,1},{3,5,1},{4,6,2},
                       {5,7,9},{5,8,7},{6,8,4},{7,9,2},{8,9,4} };
    for (int i = 0; i < e; i++) {
        int u = A[i][0], v = A[i][1], w = A[i][2];
        g[u][v] = w; indeg[v]++;
    }

    topoSort();
    if (tcnt < n) { printf("AOE 网有环，无法求关键路径\n"); return 1; }
    printf("拓扑序：");
    for (int i = 0; i < tcnt; i++) printf("v%d ", topo[i]);
    printf("\n");

    /* ve：按拓扑序取 max */
    for (int k = 0; k < tcnt; k++) {
        int u = topo[k];
        for (int v = 1; v <= n; v++)
            if (g[u][v] && ve[u] + g[u][v] > ve[v]) ve[v] = ve[u] + g[u][v];
    }
    /* vl：按逆拓扑序取 min，初值取 ve[汇点] */
    for (int i = 1; i <= n; i++) vl[i] = ve[topo[tcnt - 1]];
    for (int k = tcnt - 1; k >= 0; k--) {
        int u = topo[k];
        for (int v = 1; v <= n; v++)
            if (g[u][v] && vl[v] - g[u][v] < vl[u]) vl[u] = vl[v] - g[u][v];
    }

    printf("\n事件  ve  vl  关键?\n");
    for (int i = 1; i <= n; i++)
        printf("v%d    %2d  %2d   %s\n", i, ve[i], vl[i], ve[i] == vl[i] ? "是" : "");

    printf("\n活动  弧         w   e   l   d   关键?\n");
    for (int i = 0; i < e; i++) {
        int u = A[i][0], v = A[i][1], w = A[i][2];
        int ee = ve[u], l = vl[v] - w, d = l - ee;
        printf("a%-3d  v%d->v%-3d   %2d  %2d  %2d  %2d   %s\n",
               i + 1, u, v, w, ee, l, d, d == 0 ? "是" : "");
    }
    printf("\n最短工期 = %d\n", ve[n]);
    /* 最短工期 = 18；关键活动 a1 a4 a7 a8 a10 a11 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

n = 9
# (起点事件, 终点事件, 持续时间)
A = [(1,2,6),(1,3,4),(1,4,5),(2,5,1),(3,5,1),(4,6,2),
     (5,7,9),(5,8,7),(6,8,4),(7,9,2),(8,9,4)]
succ = {i: [] for i in range(1, n + 1)}
pred = {i: [] for i in range(1, n + 1)}
indeg = {i: 0 for i in range(1, n + 1)}
for u, v, w in A:
    succ[u].append((v, w)); pred[v].append((u, w)); indeg[v] += 1

# 1) 拓扑排序
from collections import deque
q = deque([i for i in range(1, n + 1) if indeg[i] == 0])
topo = []
while q:
    u = q.popleft(); topo.append(u)
    for v, w in succ[u]:
        indeg[v] -= 1
        if indeg[v] == 0: q.append(v)
assert len(topo) == n, "AOE 网有环"
print("拓扑序:", topo)                      # [1,2,3,4,5,6,7,8,9]

# 2) ve：按拓扑序取 max
ve = {i: 0 for i in range(1, n + 1)}
for u in topo:
    for v, w in succ[u]:
        ve[v] = max(ve[v], ve[u] + w)

# 3) vl：按逆拓扑序取 min
vl = {i: ve[topo[-1]] for i in range(1, n + 1)}
for u in reversed(topo):
    for v, w in succ[u]:
        vl[u] = min(vl[u], vl[v] - w)

print("ve:", ve)   # {1:0, 2:6, 3:4, 4:5, 5:7, 6:7, 7:16, 8:14, 9:18}
print("vl:", vl)   # {1:0, 2:6, 3:6, 4:8, 5:7, 6:10, 7:16, 8:14, 9:18}

# 4) 活动表
crit = []
for i, (u, v, w) in enumerate(A, start=1):
    e_, l_, d = ve[u], vl[v] - w, vl[v] - w - ve[u]
    if d == 0: crit.append((u, v, w))
    print("a%-2d v%d->v%d w=%2d  e=%2d l=%2d d=%2d %s" % (i, u, v, w, e_, l_, d, "关键" if d == 0 else ""))

# 5) 枚举源点到汇点的所有路径，找出最长的（= 关键路径）
def all_paths(u, end, path, total):
    if u == end:
        return [(list(path), total)]
    out = []
    for v, w in succ[u]:
        path.append(v); out += all_paths(v, end, path, total + w); path.pop()
    return out

paths = all_paths(1, 9, [1], 0)
best = max(t for _, t in paths)
print("\n工期 =", best)
for p, t in sorted(paths, key=lambda x: -x[1]):
    print("  %s 长度=%d %s" % ("->".join(map(str, p)), t, "← 关键路径" if t == best else ""))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

• AOE 网：边 = 活动（带持续时间），顶点 = 事件；只有一个源点和一个汇点，且必须是 DAG。
• 关键路径 = 从源点到汇点的最长路径，其长度 = 工程最短完成时间。
• 关键活动 ⟺ 时间余量 $d=l-e=0$。
• $ve$ 按拓扑序取 max；$vl$ 按逆拓扑序取 min；$vl(\mathrm{汇}\mathrm{点})=ve(\mathrm{汇}\mathrm{点})$。
• $e(a)=ve(\mathrm{起}\mathrm{点}\mathrm{事}\mathrm{件})$，$l(a)=vl(\mathrm{终}\mathrm{点}\mathrm{事}\mathrm{件})-\mathrm{持}\mathrm{续}\mathrm{时}\mathrm{间}$。
• 算法总复杂度 $O(n+e)$（邻接表）。

2. 解题套路

• 五步走：拓扑序 → ve（max）→ vl（min）→ 活动表 e/l/d → 串关键活动成路径。
• 手算时把 $ve$、$vl$ 两行直接标在图的顶点旁边，活动表再单独列一张，最省事。
• 检查答案：$vl(\mathrm{源}\mathrm{点})$ 应算回 0；关键路径上所有顶点都应满足 $ve=vl$。

3. 易错点

• ve 用 max、vl 用 min 记反，是最常见的失分点。记住：ve 是"等所有人干完"，取最大；vl 是"不能拖累任何人"，取最小。
• 把关键路径当成最短路径。它是最长路径；"最短工期"指的是工期下界，不是图上最短路。
• 混淆事件关键与活动关键：$ve(k)=vl(k)$ 说明事件 k 在关键路径上；关键活动要用 $e=l$ 判断。所有顶点都关键的图中，弧之间还可能有非关键活动。
• 认为关键路径只有一条。本例就有两条；压缩工期时必须同时压缩所有关键路径。
• 把 $l(a)$ 算成 $vl(i)-w$（用起点事件）。正确是 $vl(j)-w$，要用终点事件的最迟时间。
• 压缩关键活动到一定程度后，原本的非关键路径会变成新的关键路径，此时继续压原先那条不再有效。
• AOV（顶点=活动）与 AOE（边=活动）混用：拓扑排序针对 AOV，关键路径针对 AOE。

小结

• AOE 网用边表示活动、顶点表示事件；关键路径是源点到汇点的最长路径，长度即最短工期。
• 五步求解：拓扑排序 → ve（max）→ vl（min）→ 活动 e/l/d → 串出关键活动。
• 关键活动满足 $e=l$（余量为 0），可能分布在多条关键路径上，压缩工期须同时动手。
• 图的部分到此告一段落；接下来转向另一大块——查找。

下一篇：查找：顺序查找、折半查找、分块查找