Question

为了讲清楚求关键路径的算法，我还是来举个例子。假设一个学生放学回家，除掉吃饭、洗漱外，到睡觉前有四小时空闲，而家庭作业需要两小时完成。不同的学生会有不同的做法，抓紧的学生，会在头两小时就完成作业，然后看看电视、读读课外书什么的；但也有超过一半的学生会在最后两小时才去做作业，要不是因为没时间，可能还要再拖延下去。下面的同学不要笑，像是在说你的是吧，你们是不是有过暑假两个月，要到最后几天才去赶作业的坏毛病呀？这也没什么好奇怪的，拖延就是人性几大弱点之一。

这里做家庭作业这一活动的最早开始时间是四小时的开始，可以理解为0，而最晚开始时间是两小时之后马上开始，不可以再晚，否则就是延迟了，此时可以理解为2。显然，当最早和最晚开始时间不相等时就意味着有空闲。

接着，你老妈发现了你拖延的小秘密，于是买了很多的课外习题，要求你四个小时，不许有一丝空闲，省得你拖延或偷懒。此时整个四小时全部被占满，最早开始时间和最晚开始时间都是0，因此它就是关键活动了。

也就是说，我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。

为此，我们需要定义如下几个参数。
1.事件的最早发生时间etv（earliest time ofvertex）：即顶点v_k的最早发生时间。
2.事件的最晚发生时间ltv（latest time ofvertex）：即顶点v_k的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
3.活动的最早开工时间ete（earliest time ofedge）：即弧a_k的最早发生时间。
4.活动的最晚开工时间lte（latest time ofedge）：即弧a_k的最晚发生时间，也就是不推迟工期的最晚开工时间。

我们是由1和2可以求得3和4，然后再根据ete[k]是否与lte[k]相等来判断a_k是否是关键活动。