第六章 图 十、关键路径

目录

开始顶点（源点)：

结束顶点（汇点)：

关键路径：

一、求所有事件的最早发生时间

找到拓扑排序序列：

二、求所有事件的最迟发生时间

找到逆拓扑序列：

三、求所有活动的最早发生时间(等于活动a起始的事件的最早发生时间；例a1的最早发生时间是V1的最早发生时间)

四、求所有活动的最迟发生时间（就是小a所指向的事件的最迟发生时间减去活动的路径长度）

五、求所有活动的时间余量

l(k) - e(k) = 1 - 0 = 1;

六、注意

---

开始顶点（源点)：

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点)，它表示整个工程的开始;

结束顶点（汇点)：

也仅有一个出度为0的顶点，称为结束顶点（汇点)，它表示整个工程的结束。

关键路径：

（1）从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动.

（2）完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长

一、求所有事件的最早发生时间

例：

找到拓扑排序序列：

V1的最早发生时间：没有前驱，所以ve(1)=0;

V3的最早发生时间：前驱为V1，所以ve(3)=0+2=2;

V2的最早发生时间：前驱为V1，所以ve(2)=0+3=3;

V5的最早发生时间：前驱为V2，所以ve(5)=ve(2)+3=3+3=6; 

V4的最早发生时间：前驱为V2和V3，所以ve(4)=max{2+3,4+2}=6;

V6的最早发生时间：前驱为V3,V4,V5，所以ve(6)=max{3+2,2+6,1+6}=8;

二、求所有事件的最迟发生时间

找到逆拓扑序列：

汇点的最早发生时间和最迟发生时间相等

V6的最迟发生时间：8

V5的最迟发生时间：8-1=7

V4的最迟发生时间：8-2=6

V2的最迟发生时间：min{ 6 - 2 , 7 - 3 } = 4

V3的最迟发生时间：min{ 6 - 4 , 8 - 3 } = 2

V1的最迟发生时间：min{ 2 - 2 , 4 - 3 } = 0

三、求所有活动的最早发生时间(等于活动a起始的事件的最早发生时间；例a1的最早发生时间是V1的最早发生时间)

根据上图可写出：

四、求所有活动的最迟发生时间（就是小a所指向的事件的最迟发生时间减去活动的路径长度）

a4 = 7 - 3 = 4

五、求所有活动的时间余量

l(k) - e(k) = 1 - 0 = 1;

六、注意