关键路径

AOE-网,顶点表示事件,弧表示活动,权表示活动持续的时间。

路径长度最长的路径称为关键路径

步骤:先求最早发生时间然后求最晚发生时间,二者相等的活动为关键路径上的活动

求最早发生时间是用拓扑排序,ve要选较大的,例如图中选到ve(4)时,应该选红线还是黄线呢?ve(1)+1=4 ve(2)+3=7  应该选黄线7,因为如果比7小例如4的时候发生,那么事件2还没结束就开始了事件4显然是不行的,所以求最早发生时间时,如果对于一个活动有多个选择,应该选择大的,不能太早,太早有些活动还没准备好

最晚发生时间用逆拓扑排序,也就是从后面开始,ve要选小的,例如求vl(7)时,应该选择黄线还是红线呢? 如果选黄线最晚发生时间就是22-4=18,红线21-10=11,如果选了黄线那么就是时间点18发生,它就不能保证后一个事件的最晚发生时间了,应该选小的,不能太晚

最早发生时间和最晚发生时间求出后进行比较,则可得到关键路径

原文地址:https://www.cnblogs.com/Liu269393/p/10226957.html