可能要求解两种问题,一种是完成所有的任务的最早时间,这个其实只是求解关键路径问题的一部分,另一种是要输出关键路径(关键路径不一定是唯一的)
定义:关键路径就是求始点到终点的一条最长路径,通过求各顶点的最早完成时间来求关键路径
两个重要概念(容易混淆,容易越想越糊涂)
1.最早完成时间:自始点(记为V1)开始沿最长路径(按权计算)到达Vi所需要的时间,成为Vi的最早完成时间,记为TE[i]
TE[1]=0; (准确来说应该是拓扑排序中的第一个点为0,而第1个点不一定只有1个,而且编号不一定为1,这里只是举一个例子,另外时间也不一定是0,看从什么时候开始计时)
TE[j] = max (TE[i] + Wij) (有向边i--->j)
如果是要找所有任务最早什么时候可以全部做完,其实就是找最大的TE[i]
2.最晚完成时间:在保证终点Vn的最早完成时间不增加的条件下,自V1最迟到达Vi的时间,记为TL[i]
TL[n]=TE[n]; (别忘了看定义,是保证最后一个点的最早完成时间不增加的条件下,否则的话就没意义了)
TL[i] = min ( TL[j] - Wij) (有向边i--->j)
3.缓冲时间:由定义可知 TS[i] = TL[i]-TE[i] >= 0 , TS[i]为点i的缓冲时间
关键路径上的点就是缓冲时间为0的点(也就是说这些事件没有拖拉的余地,一旦这个时间拖拉了,整个任务将被延迟完成)
两句话总结就是:
1.一个事件被一些事件约束着,它什么时候能开始做,决定于这些约束事件最晚完成的那个时刻(最早完成时间)
2.一个事件是一些事件的约束条件(当然那些事情可能不止一个约束条件),它企图拖拉点完成任务,但是至少要保证它的所有后续事件能够在一定时间范围最后完成,也就是要找到最早完成的那个时刻(最晚完成时间)
再不行,画个时间轴吧