目录#

[[toc]]

概念#

AOE 网：

• 顶点表示事件（某个时刻任务都完成的状态）。
• 边表示活动（一项具体工作），边上数字为活动所需时间。
• 最早开始时间(E)：在保证所有前置活动都完成的情况下，该活动可以最早开始的时间。
• 最迟开始时间(L)：在不延误整个工程总工期的前提下，该活动最晚必须开始的时间。

名称	含义
AOE 网	一种有向无环图，用于表示带有时间约束的工程计划。顶点表示事件，边表示活动，边上标注活动持续时间。
事件（Event）	一个时刻，表示若干前置活动全部完成的状态。事件本身不消耗时间。
活动（Activity）	从一个事件到另一个事件的有向边，表示必须完成的一项工作，并附有持续时间。
源点	整个工程的起点事件（入度为 0）。
汇点	整个工程的终点事件（出度为 0）。
关键路径	从源点到汇点的最长路径。它决定了工程的最短工期。

AOE 网是网络计划技术（PERT/CPM）的基础模型，主要用于项目进度控制与关键路径分析。

关键时间参数#

$以一个活动 <i,j> 为例（起点事件 i，终点事件 j，工期 tij）：$

符号	含义	求法
ve(i)	事件 i 的最早发生时间。保证所有前置活动完成后，i 最早可以发生的时间。	正向推导：ve(j)=max[ ve(i)+t(i,j) ]
vl(i)	事件 i 的最迟发生时间。在不延误总工期的前提下，i 最晚必须发生的时间。	逆向推导：vl(i)=min[ vl(j)-t(i,j) ]
E(i,j)	活动 <i,j> 的最早开始时间。	E(i,j) = ve(i)
L(i,j)	活动 <i,j> 的最迟开始时间。	L(i,j) = vl(j) - t(i,j)
e(i,j)	活动 <i,j> 的最早完成时间。	e(i,j) = E(i,j) + t(i,j)
总时差	活动开始时间可延迟的最大时间，不影响总工期。	L(i,j) - E(i,j)

拓扑排序#

拓扑排序：对一个有向无环图的所有顶点排一个线性顺序，使得对图中每条有向边 (u → v)，顶点 u 都排在 v 的前面。

换句话说：

• 有依赖的任务必须排在依赖它的任务前面。
• 只要保证每个边的方向都“从左到右”即可。

① 入度法（Kahn 算法）#

• 计算每个节点的入度（有多少前驱）。
• 把所有入度为 0 的节点入队。
• 反复：
  • 取出一个入度为 0 的节点放到结果序列。
  • 删除它的所有出边，对目标节点入度减 1。
  • 若某节点入度变 0，入队。
• 直到队列空。

复杂度：O(V + E)

② 深度优先搜索 (DFS) 法#

• 对每个未访问节点执行 DFS。
• 在递归返回时将节点压入栈。
• 最后把栈倒出来就是拓扑序。

复杂度：O(V + E)

场景	作用
编译依赖	先编译被依赖的模块，再编译依赖它的模块。
任务调度	计算任务的执行顺序，如软件构建、流水线生产。
项目管理	在 AOE 网络中正向推算最早开始时间就是一次拓扑排序。
版本控制	处理代码依赖关系。

关键路径求法（CPM 算法）#

核心：一次正推 + 一次逆推

① 正向推算最早时间#

• 从源点开始，拓扑排序。

• ve(源) = 0

  ve(j) = max{ve(i) + t(i,j)} —— 取所有前驱 i 的最大值。

• 最后得到 工期 = ve(汇点)。

② 逆向推算最迟时间#

• vl(汇) = 工期

  vl(i) = min{vl(j) - t(i,j)} —— 取所有后继 j 的最小值。

③ 求每条活动的 E 和 L#

• E(i,j) = ve(i)
• L(i,j) = vl(j) - t(i,j)

④ 关键路径判定#

• 若 E(i,j) == L(i,j)，则 <i,j> 是关键活动。
• 从源点沿关键活动走到汇点得到关键路径。

例如：

活动 d 的最早开始时间 = 2 号事件 的 最早时间 = MAX(v(i,2)+t(i,2)) = 12

活动 d 的最迟开始时间 = 4 号 事件 - 7 (逆）

第一步：算每个事件的最早发生时间 ve（正向推一次）

1. ve(1)=0
2. ve(3)=ve(1)+8=8
3. ve(2)=max{ve(1)+3 , ve(3)+4} = max{3,12} = 12
4. ve(4)=ve(2)+7=19
5. ve(5)=max{ve(2)+6 , ve(3)+10} = max{18,18} = 18
6. ve(6)=max{ve(4)+6 , ve(5)+9} = max{25,27} = 27

整个工程的工期 = ve(6) = 27

👉 由此得出

E(d) = ve(2) = 12

---

第二步：算每个事件的最迟发生时间 vl（逆向推一次）

1. vl(6)=27
2. vl(4)=vl(6)-6=21
3. vl(5)=vl(6)-9=18
4. vl(2)=min{vl(4)-7 , vl(5)-6} = min{14,12} = 12
5. vl(3)=min{vl(2)-4 , vl(5)-10} = min{8,8} = 8
6. vl(1)=min{vl(2)-3 , vl(3)-8} = min{9,0} = 0

👉 由此得出

L(d) = vl(4) - 7 = 21 - 7 = 12

仍然需要逆推到 d 的终点 4，

• 找 4 的后继（只有 6）
• vl(4) = vl(6) - 6
• 再算 vl(6)（可用关键路径或已知总工期）

在这题里正好总工期 27 已知或易算，因此直接

vl(4) = 27 - 6 = 21

L(d) = 21 - 7 = 12

应用场景#

典型场景	说明
房屋、桥梁、道路施工	每个工序（打地基、浇筑、装修等）作为活动，边权是施工时间。
大型工程项目	电厂建设、地铁修建、航天工程等，需要准确评估总工期和关键环节。
研发项目	硬件研发、芯片流片，每个实验、设计阶段都是节点之间的有向活动。

• PERT / CPM：经典项目管理方法，本质上就是在 AOE 网上做关键路径分析。
• 现代调度框架：Airflow、Prefect、Dagster、Luigi 等都以 DAG（有向无环图）为核心思想，与 AOE 网等价。
• 甘特图：最终可视化结果之一，AOE 网提供计算依据。

AOE 网络是一种面向工程和任务依赖的通用时间规划工具：

• 图论视角：有向无环图 + 边权。
• 关键任务管理：计算总工期、找出关键路径。
• 广泛落地：建筑工程、IT 软件开发、制造生产、交通物流、科研与大型活动等。