关键路径（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) 的活动，即为关键活动，关键活动构成关键路径

cpp

#include <cstring>
#include <stack>
#include <queue>
using namespace std;

const int MAXV = 1005;

struct Edge {
    int to, w, next;
} edges[MAXV * MAXV];

int head[MAXV], cnt;
int inDeg[MAXV];
int ve[MAXV], vl[MAXV];  // 事件最早/最晚发生时间
int n, m;                 // n个事件, m个活动

void addEdge(int u, int v, int w) {
    edges[cnt] = {v, w, head[u]};
    head[u] = cnt++;
    inDeg[v]++;
}

// 拓扑排序 + 求 ve[]
bool topoSort(stack<int>& topoStack) {
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (inDeg[i] == 0) q.push(i);

    int count = 0;
    memset(ve, 0, sizeof(ve));

    while (!q.empty()) {
        int u = q.front(); q.pop();
        topoStack.push(u);  // 记录拓扑序，用于逆序求 vl
        count++;
        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)
                q.push(v);
        }
    }
    return count == n;  // 判断是否有环
}

// 求关键路径
void criticalPath() {
    stack<int> topoStack;
    if (!topoSort(topoStack)) 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[]
    while (!topoStack.empty()) {
        int u = topoStack.top(); topoStack.pop();
        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 用边表示活动）
关键路径不唯一时，缩短工期的条件分析（需缩短所有关键路径的公共关键活动）
关键路径算法与拓扑排序的关系（关键路径以拓扑排序为基础）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

关键路径（AOE 网） ​

为什么需要关键路径 ​

核心思想 ​

交互可视化 ​

操作详解 ​

基本概念 ​

求关键路径过程 ​

时间余量分析 ​

复杂度分析 ​

考研高频考点 ​

相关文章