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

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

```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.POSITIVE_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[][] mustCompletedBefore) {
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 < mustCompletedBefore[i].length; j++) {
int successor = mustCompletedBefore[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};
int[][] before = {{1, 7, 9}, {2}, {}, {}, {}, {}, {3, 8}, {3, 8}, {2}, {4, 6}};
CPM cpm = new CPM(duration, before);
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一气呵成，中间毫无停顿。而且其他任务在这条生产线执行过程中均已完成！

END.

0 条评论

• ### 数据咖课堂：R语言十八讲(十八)—R实现主成分分析

? 之前我们在十七讲,将主成分分析的原理和计算过程了解了一遍,今天我们用工具R来实现这一模型.由于R软件中有多个函数可以处理这件事情,所以我们选用两个主要的来...

• ### 11个你可能不知道的Python库

现在有如此之多的Python包，几乎没有人能够全盘掌握。 光是PyPI就可单独列出47,000个包！ 近日，听到很多数据科学家切换到Python的消息，我不由地...

• ### 【吐槽】大数据择偶 让你脑洞大开

女博士嫁不出去么，姐弟念不会长久，恋爱多久了在一起生活？就让大数据带你走进互联网时代的择偶指南！上海市复旦大学社会科学数据研究中心在本市找了80个社区、3311...

• ### Elasticsearch聚合 之 DateRange日期范围聚合

相比于range聚合，date range就是范围可以由时间来指定。 例如： { "aggs":{ "range":{ ...

• ### 算法推荐 — 协同过滤

求解评分矩阵的一种典型方法是：ALS，在spark-mllib库中有实现好的api；

• ### [经典收藏]终极RPA术语表：机器人流程自动化的基础概念

随着自动化和识别技术超越了制造工厂开始进入知识工作者的办公室环境，公司领导者必须知道的术语也会增加。RPA行业使用了许多源自传统的物理机器人应用的术语 – 类似...

• ### RPA机器人流程自动化项目顺利应用的4个典型场景

RPA（机器人流程自动化）现在正迎来一个全新的发展期。特别是在当前越发严峻的市场大环境下，企业降本增效的意愿迫切，而RPA则给企业带来了变革性的解决方案。

• ### 进程、线程、锁的概念

上周五终于改好bug，想着把代码同步到个人GitHub上面，就随手 git push同步到远程。然而万万没想到，之前 touch过一个 information....

• ### Hive万亿级表联合分析故障排查与优化过程

随着大数据技术日趋成熟，行业生态愈发完善，腾讯云大数据团队服务的大客户越来越多。在笔者服务的众多大客户之中，PB级海量数据已经成为常态。笔者负责大数据技术支持的...