AOE网与关键路径

路径"/>

AOE网与关键路径

AOE网（Activity On Edge Network）

是一个有向图：

1. 顶点：事件;
2. 弧：活动；
3. 权：完成该活动所需的时间；
4. 源点：工程的开始，入度为0的事件，AOE网只能有一个源点
5. 汇点：工程的结束，出度为0的事件，AOE网只能有一个汇点
6. 每一事件v表示：以它为弧头的所有活动已经完成
7. 每一事件v表示：以它为弧尾的所有活动可以开始

例子：

上图为一个AOE网
有4个事件： v 1 ， v 2 ， v 3 ， v 4 v_1， v_2， v_3， v_4 v1​，v2​，v3​，v4​ （ v 1 v_1 v1​为源点， v 4 v_4 v4​为汇点）
有4个活动： a 1 , a 2 , a 3 , a 4 a_1, a_2, a_3, a_4 a1​,a2​,a3​,a4​
其中：事件 v 3 v_3 v3​表示： a 2 a_2 a2​已完成， a 4 a_4 a4​可以开始

AOE网可解决如下问题：

1. 估算最短工期：从源点到汇点至少需要多少时间
2. 找出哪些活动是影响整个工程进展的关键

关键路径 Critical Path

1. 路径长度：路径上各活动持续时间的总和
   即：路径上所有弧的权值之和
2. 关键路径：从源点到汇点之间路径长度最长的路径
   注意：关键路径不一定唯一
3. w ( j , k ) w(j,k) w(j,k) 表示活动 &lt; j , k &gt; &lt;j,k&gt; <j,k>的持续时间

例子：

1. 事件（ v j v_j vj​）的最早发生时间： E v ( j ) E_v(j) Ev​(j)
   从源点到 v j v_j vj​ 的最长路径长度
2. 活动（ a i a_i ai​）的最早开始时间： E a ( i ) E_a(i) Ea​(i)
   等于该活动的弧尾事件（ v j v_j vj​）的最早发生时间
   例子：
   若以符号 &lt; j , k &gt; &lt;j, k&gt; <j,k>表示活动 a i a_i ai​，则有： E a ( i ) = E v ( j ) E_a(i) = E_v(j) Ea​(i)=Ev​(j)
3. 事件（ v k v_k vk​）的最迟发生时间： L v ( k ) L_v(k) Lv​(k)
   在不推迟整个工期的前提下，该事件最迟必须发生的时间
4. 活动（ a i a_i ai​）的最迟开始时间： L a ( i ) L_a(i) La​(i)
   该活动的弧头事件最迟发生时间与该活动的持续时间之差
   即： L a ( i ) L_a(i) La​(i) = L v ( k ) L_v(k) Lv​(k) - （ a i a_i ai​ 的持续时间）
5. 关键活动： L a ( i ) L_a(i) La​(i) = E a ( i ) E_a(i) Ea​(i) 的活动
6. 由此：在AOE网中找关键活动问题可转化为
   求满足如下条件的活动： L a ( i ) L_a(i) La​(i) = E a ( i ) E_a(i) Ea​(i)
   其中： E a ( i ) E_a(i) Ea​(i) = E v ( j ) E_v(j) Ev​(j)， L a ( i ) L_a(i) La​(i) = L v ( k ) L_v(k) Lv​(k) - （ a i a_i ai​ 的持续时间）
   因此需首先求出事件的最早、最迟发生时间

关键路径算法设计

1. 从 E v ( 1 ) = 0 E_v(1)=0 Ev​(1)=0 开始，递推计算出各事件的最早发生时间
   事件（ v i v_i vi​）的最早发生时间：从源点到 v i v_i vi​ 的最长路径长度
2. 从 L v ( n ) = E v ( n ) L_v(n) = E_v(n) Lv​(n)=Ev​(n)开始，计算出各事件的最迟发生时间
   L v ( i ) L_v(i) Lv​(i)：事件（ v i v_i vi​）最迟必须发生的时间
   E v ( i ) E_v(i) Ev​(i)：事件（ v i v_i vi​）的最早发生时间
3. 计算出AOE网络中各活动的最早、最迟开始时间
4. 找出 E a ( i ) = L a ( i ) E_a(i) = L_a(i) Ea​(i)=La​(i) 的活动，即为关键活动
5. 由关键活动组成的从源点到汇点的路径即为关键路径
   例子:
   
   

结论

在有多条关键路径时，缩短那些存在于所有关键路径上的关键活动，才能缩短整个工期