关键路径

基本概念：

• 事件最早发生时间 $ve(i)$：

  • 从源点向汇点看（正向）。
  • 取最大值：$ve(j)=\max \{ve(i)+\text{weight}(i,j)\}$。
  • 直观理解：只有所有前驱任务都做完了，这个点代表的事件才能发生。

• 事件最迟发生时间 $vl(i)$：

  • 从汇点向源点看（反向）。
  • 取最小值：$vl(i)=\min \{vl(j)-\text{weight}(i,j)\}$。
  • 直观理解：为了不耽误总工期，这个事件最晚必须在什么时候发生。

• 活动最早开始时间 $e(k)$：

  • 即该活动起点事件的 $ve$。

• 活动最迟开始时间 $l(k)$：

  • 即该活动终点事件的 $vl$ 减去活动持续时间。

• 对象：AOE网 (边表示活动，顶点表示事件)。

• 核心概念：

  • 关键路径：源点到汇点路径长度最长的路径（决定工程最短工期）。
  • 关键活动：$e(i)=l(i)$ 的活动（最早开始时间 = 最迟开始时间）。

• 求解步骤 (计算题高发)：

  1. 正向递推求事件最早发生时间 $ve(j)$：取前驱的最大值（必须等所有前驱完成）。
  2. 反向递推求事件最迟发生时间 $vl(j)$：取后继的最小值（不能耽误工期）。
  3. 计算活动的最早 $e(i)$ 和最迟 $l(i)$。
  4. 找出 $e(i)=l(i)$ 的活动即为关键活动。