# 数据结构与算法-关键路径

www.MyException.Cn  网友分享于：2013-10-08  浏览：0次

# 数据结构与算法--关键路径

## 通过求解最长路径得到关键路径

``````package Chap7;

/**
* 求无环有向图的最长路径
*/
public class AcycliLP {
private DiEdge[] edgeTo;
private double[] distTo;

public AcycliLP(EdgeWeightedDiGraph<?> graph, int s) {
edgeTo = new DiEdge[graph.vertexNum()];
distTo = new double[graph.vertexNum()];

for (int i = 0; i < graph.vertexNum(); i++) {
// 1. 改成了负无穷
distTo[i] = Double.NEGATIVE_INFINITY;
}

distTo[s] = 0.0;
// 以上是初始化
TopoSort topo = new TopoSort(graph);

if (!topo.isDAG()) {
throw new RuntimeException("该图存在有向环，本算法无法处理！");
}

for (int v : topo.order()) {
relax(graph, v);
}
}

private void relax(EdgeWeightedDiGraph<?> graph, int v) {
for (DiEdge edge : graph.adj(v)) {
int w = edge.to();
// 2、若路径更长就更新
if (distTo[v] + edge.weight() > distTo[w]) {
distTo[w] = distTo[v] + edge.weight();
edgeTo[w] = edge;
}
}
}

public double distTo(int v) {
return distTo[v];
}

public boolean hasPathTo(int v) {
return distTo[v] != Double.NEGATIVE_INFINITY;
}

public Iterable<DiEdge> pathTo(int v) {
if (hasPathTo(v)) {
for (DiEdge edge = edgeTo[v]; edge != null; edge = edgeTo[edge.from()]) {
path.push(edge);
}
return path;
}
return null;
}
}``````

``````package Chap7;

public class CPM {
private AcycliLP lp;
private int s; // 虚拟的起点
private int t; // 虚拟的终点
private int jobsNum; // 任务个数

public CPM(double[] jobDuration, int[][] successorAfter) {
jobsNum = jobDuration.length;
// 设置两个虚拟顶点，代表起点和终点
EdgeWeightedDiGraph<?> graph = new EdgeWeightedDiGraph<>(jobsNum + 2);

s = jobDuration.length; // 起点
t = s + 1; // 终点

for (int i = 0; i < jobsNum; i++) {
// 每个顶点都可能成为最先开工的，所以虚拟起点指向所有顶点，且费时都为0
// 每个顶点都可能成为工程收尾的活动，所有顶点都指向该虚拟终点，费时自然是每个活动所持续的时间
// 任务i必须在任务j之前完成， 即加入i -> j的有向边
for (int j = 0; j < successorAfter[i].length; j++) {
int successor = successorAfter[i][j];
}
// 找到到每个活动的最长路径
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};
// 必须在这些任务之前完成，如successorAfter[0]表示任务0的后继任务1、7、9，也就是说0必须在1、7、9之前做完
// {} 表示该任务不要求在哪个任务执行前就得完成，说明它可能是作为收尾的任务
int[][] successorAfter = {{1, 7, 9}, {2}, {}, {}, {}, {}, {3, 8}, {3, 8}, {2}, {4, 6}};
CPM cpm = new CPM(duration, successorAfter);
cpm.printJobExecuteOrder();
}

}``````

• 虚拟起点到所有顶点的边，且权值为0；
• 所有顶点到虚拟终点的边，且权值为顶点任务持续时间。
• 某任务v必须在一些任务之前完成的边，且权值为任务v的持续时长。比如0必须在1、7、9之前，则增加0 -> 1，0 -> 7，0 -> 9边，且权值都为任务0的持续时长。

``````各任务开始时间表：
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

0 -> 9 -> 6 -> 8 -> 2一气呵成，中间毫无停顿。而且其他任务在这条生产线执行过程中均已完成！

by @sunhaiyu

2017.9.29