6.4.5_关键路径

AOE网：

用E=Edge表示活动，AOV网是用Vertex顶点表示活动

仅有一个入度=0的顶点叫开始顶点(源点)，出度=0的顶点叫结束顶点(汇点)

各条边表示活动，边上的权值表示完成该活动的开销，各顶点表示事件，事件是就发生在某个时刻，活动是持续一段时间的

1.只有事件发生后才可进行活动，如下只有开始事件发生后才可打鸡蛋或者洗番茄

2.只有指向该顶点事件的各边所代表的活动都完成了指向的事件才可发生，如打鸡蛋和切番茄活动都完成后才可发生可以炒了事件

3.从一个顶点往外指出多条边，意味着这些边上的活动可以并行进行，比如开始事件发生后，打鸡蛋和切番茄可以并行执行

关键路径：

从源点到汇点有多条路径，路径长度(经过的边上的权值之和)最大的一条叫关键路径，关键路径上的活动称为关键活动，关键路径意味着要完成某个事儿至少需要关键路径长度时间，关键活动意思是要完成某个事儿这些活动都不能少

如下图有：开始->可以切了->可以炒了->结束、开始->打鸡蛋->可以炒了->结束两条路径，前一条路径长度:1+3+2=6,后一条路径长度：2+2=4，即前一条为关键路径

活动余量=最迟开始时间-最早开始时间，活动余量=0的活动表示是关键活动，即不能拖延的活动

汇点的最迟发生时间=汇点的最早发生时间

求关键路径步骤：

各个事件发生的最早开始时间=对应各个活动的最早开始时间，从开始顶点推算出各顶点最早开始时间，通过结束顶点逆推出各个顶点的允许的最迟发生时间，进而得出各个活动的最迟发生时间

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

还得求拓扑序列，再按照拓扑序列去求各个顶点的最早发生时间

求所有事件的最迟发生时间(取最小的)：

还得求逆拓扑序列，再按照逆拓扑序列去求各个顶点的最迟发生时间

 

求所有活动的最早发生时间：

活动发生的最早时间=活动的弧尾连接的顶点的最早发生时间，如下图中的a4活动最早时间为弧尾连接的V2的最早发生时间

 

求所有活动的最迟发生时间：

 活动发生的最迟时间=活动指向顶点的最晚发生时间-活动所在边的权值

求所有活动的时间余量：

 活动的时间余量=活动的最晚发生时间-活动的最早发生时间

找到时间余量=0的活动，这些活动所在的边连接起来的路径就是关键路径

关键活动、 关键路径的特性：

当关键活动的时间被缩短到一定时间时可能会变成非关键活动，此时关键路径也会发生变化，如下切番茄由关键活动压缩时间到0.5，此时洗番茄+打鸡蛋+炒菜=1+0.5+2=3.5<打鸡蛋+炒菜=2+2=4，此时关键路径已经发生改变，因为切番茄已经不是关键活动，所以继续缩短切番茄的时间也不会影响最后的结束时间了 

在一个aoe网中可能有多条关键路径：

多条关键路径下，只缩短一条关键路径上的关键活动的时间并不能缩短整个工期，只有把所有关键路径上的某些或全部关键活动时间都缩短或者把把某个在所有关键路径上的关键活动的时间缩短才能缩短整个工期

知识回顾：

 

水一篇文字。。。。。。。。。。。