加权有向图----关键路径算法

优先级限制下的并行任务调度：给定一组需要完成的任务和每个任务所需要的时间，以及一组关于任务完成的先后次序的优先级限制。在满足条件的前提下应该如何在若干相同的处理器上安排任务并在最短的时间内完成任务？

“关键路径”算法可以在线性时间内解决此问题。这个问题与无环加权有向图的最长路径问题是等价的。

为了设计求关键路径的动态规划算法，现在定义三个术语：

事件i可能最早发生的时间earliest(i): 是指从开始结点s到结点i的最长路径的长度。

事件i允许的最迟发生时间latest(i): 是值不影响效益的条件下，事件i允许发生的最晚时间。

关键活动： 处于关键路径上的活动是关键活动，它必须准时启动，否则就会使任务延期。

earliest()计算方法：

• earlist(0) = 0
• earlist(j) = max{earlist(i) + w(i,j)}    0<j<V, i∈P(j)   注：P(j)是拓扑图中与顶点j直接相邻的前一顶点集

latest()计算方法：

• latest(V-1) = earliest(V-1)
• latest(i) = min{latest(j) - w(i,j)}   0<=i<V-1,j∈S(i)    注：S(i)是拓扑图中与i直接相邻的后一结点集

关键活动计算方法：

若latest(j) - earliest(i) = e.weight (e为顶点i和j之间的有权边），则边e是关键活动。对于关键路径上的每一个关键结点i，都有latest(i) = ealiest(i).

关键路径算法基本步骤：

1. 确认有向图G是无环图，并进行拓扑排序;
2. 按拓扑次序计算earliest(i), 0<=i< V-1;
3. 按逆拓扑排序计算latest(i), 0<=i< V-1;
4. 计算latest(j) - earliest(i)，判断是否为关键活动。