关键路径是从源点到汇点的所包含的活动时间最长的一条路径,之所以要求是最长的是因为,在这工程中,我们除了要实现从起始点到最终点这个任务外,还要将这个图中的所有活动全部完成,只有选取最长的路径最为关键路径,其余的活动才能做完
在该网络中,顶点我们称为事件,边我们称为活动。
事件最早可能的开始时间$Ve[i]$是从源点到该事件的最长路径,最所以是最长的原因和关键路径相同,我们要保证所有可以到达当前事件的路径上的事件必须在该事件前完成,比如
$v0 \to v1 \to v2 \to v3$
$v0 \to v1 \to v4 \to v2 \to v3$ 是全部的从源点到当前事件v3的路径,那么在v3开始前要求这两条路径上的事件全部完成
事件最晚的开始时间$Vl[i]$是在全部事件能在关键路径时长下全部完成的前提下最晚的开始时间,比如当前$v3$的最早开始时间是$4$,但是$v3$不在关键路径中,而关键路径的长度是$7$,也就是说包含$v3$的这条路的时间花费会比关键路径小,而这些少的时间($3$)就可以被 $v3$拿来“偷懒”,在保证其前面事件都能完成和不耽误整体时间的前提下完开始一会,也就是最晚开始时间
在这个网路中我们不光有事件,还有活动,也就是边
活动最早开始$e[k]$的时间是当前活动的起始顶点的最早开始时间,这很好理解,因为事件的开始就代表着活动的开始
活动的最晚开始时间$l[k]$是在不会影响整体时间的前提下,一个活动的最晚开始时间,这里要注意的是,一个活动的最晚开始时间不一定是其起始顶点的最晚开始时间,这是因为一个顶点的最晚开始时间要能保证其后面的事件都能完成,如果其起始顶点有着多个活动,则$vl[i]=min(vl[j]-dur(i,j)) \space , \space i \to j \in E$,所以起始顶点对应的最晚开始时间可能要小于当前活动的最晚开始时间。
时间余量是$l[k]-e[k]$,若余量为0,则代表这个活动在关键路径上
要注意的是源点(汇点)的最早和最晚开始时间是一样的