正文
各条从s到t的路径中（想象成各条生产线），找出最长的那条（费时最长的那条生产线），这条0 -> 9 -> 6 -> 8 -> 2就是关键路径，按照这个顺序执行任务就能使得完成整个工程总时间最短。
我们用代码测试一下。
package Chap7;
public class CPM {
private AcycliLP lp;
private int s; // 虚拟的起点
private int t; // 虚拟的终点
private int jobsNum; // 任务个数
public CPM(double[] jobDuration, int[][] mustCompletedBefore) {
jobsNum = jobDuration.length;
// 设置两个虚拟顶点，代表起点和终点
EdgeWeightedDiGraph> graph = new EdgeWeightedDiGraph<>(jobsNum + 2);
s = jobDuration.length; // 起点
t = s + 1; // 终点
for (int i = 0; i < jobsNum; i++) {
// 每个顶点都可能成为最先开工的，所以虚拟起点指向所有顶点，且费时都为0
graph.addDiEdge(new DiEdge(s, i, 0.0));
// 每个顶点都可能成为工程收尾的活动，所有顶点都指向该虚拟终点，费时自然是每个活动所持续的时间
graph.addDiEdge(new DiEdge(i, t, jobDuration[i]));
// 任务i必须在任务j之前完成， 即加入i -> j的有向边
for (int j = 0; j < mustCompletedBefore[i].length; j++) {
int successor = mustCompletedBefore[i][j];
graph.addDiEdge(new DiEdge(i, successor, jobDuration[i]));
}
// 找到到每个活动的最长路径
lp = new AcycliLP(graph, s);
}
}
public void printJobExecuteOrder() {
System.out.println("各任务开始时间表：");
for (int i = 0; i < jobsNum; i++) {
System.out.println(i + ": " + lp.distTo(i));
}
System.out.println("\n按照以下顺序执行任务，开始时间相同的任务同时执行。");
for (DiEdge edge : lp.pathTo(t)) {
// 遇到起点不打印箭头
if (edge.from() == s) {
System.out.print(edge.to());
}
// 最后一个任务在前一个顶点的就打印过了，遇到最后一条边换行就行
else if (edge.to() == t) {
System.out.println();
} else {
System.out.print(" -> " + edge.to());
}
}
System.out.println("总共需要" + lp.distTo(t));
}
public static void main(String[] args) {
// 每个任务的持续时间
double[] duration = {41.0, 51.0, 50.0, 36.0, 38.0, 45.0, 21.0, 32.0, 32.0, 29.0};
int[][] before = {{1, 7, 9}, {2}, {}, {}, {}, {}, {3, 8}, {3, 8}, {2}, {4, 6}};
CPM cpm = new CPM(duration, before);
cpm.printJobExecuteOrder();
}
}
根据任务表，给图增加边。
接下来通过AcycliLP类求得关键路径，distTo[i]就表示i任务的开始时间，distTo[t]表示做完整个工程需要的最短时间；pathTo[i]表示执行到任务i的关键路径，自然pathTo[t]就是整个工程的关键路径。
上面的代码会打印如下结果：
各任务开始时间表：
0: 0.0
1: 41.0
2: 123.0
3: 91.0
4: 70.0
5: 0.0
6: 70.0
7: 41.0
8: 91.0
9: 41.0
按照以下顺序执行任务，开始时间相同的任务同时执行。
0 -> 9 -> 6 -> 8 -> 2
总共需要173.0
可以清楚地看到每个任务应该在什么时刻开始动工，只要按照0 -> 9 -> 6 -> 8 -> 2这样顺序执行就好。而且，有些任务开始时间一样，表示我们应该同时执行它们以节省时间。所以最后的方案是：0、5最先并同时执行，只要0做完了，就开始同时执行1、7、9，只要9做完了立刻同时执行4、6，一旦6做完了同时执行3、8，8只要完工紧接着做2，最后等待2也终于做完，整个工程竣工！需要的最短时间为173.0。
关键路径中的任务都是做完后就立刻执行下一个的（比如0执行完立刻执行9，9完工立刻执行6…），不用等待和它一起开工的其他任务也做完，因为这些任务在花费最长时间的这条关键路径上，它们迟早都能做完的。因此关键路径中，各个关键任务是不会有空闲和等待时间。如下图是上面任务表的执行流程
0 -> 9 -> 6 -> 8 -> 2一气呵成，中间毫无停顿。而且其他任务在这条生产线执行过程中均已完成！
End
