我们通常听得最多的就是最短路径的应用了，但是最长路径却很少听说过，今天就跟大家说说一个最长路径应用的例子。你可能会说不就是将最短路径求法变成最长路径么，就是一个镜像问题呀。哎，虽然主旨上差不多，但是这个例子还是要变一变的，要是这么简单这篇博客就不写出来浪费大家时间啦。
问题
假设现在有 A, B, C, D, E 五个任务，这些任务的依赖关系如下图所示，A -> B 表示先完成 A 才能做 B。每个任务都有自己的完成时间，任务上面的数字就是完成时间。问：怎样规划这些任务的完成顺序才能以最短时间做完呢？
这里加个前提，任务是可以同时做的。
想法
要是肉眼观察我们很快知道答案：A, D 先做，A 完了再做 B，同时做 E，最后做 C，总的完成时间是
| 完成时间 | 正在做的任务 |
|---|---|
| 0 ~ 5 | A, D |
| 5 ~ 8 | B, D |
| 8 ~ 12 | B, E |
| 12 ~ 18 | C |
一共为 18。
这个看起来还有点拓扑排序的味道呀，因为都是要从入度为 0 的节点开始，但是不同的是这次要 A 和 D 同时出发才能求时间呀。
新的图结构
现在我们改变一下上面的图
- 首先添加首尾两个节点 S 和 T
- 在每个任务之间加一个节点，同时将任务作为边，任务完成时间作为边的权重
- 每个节点的意义变成了做了 n 秒（n 秒为任务完成后的 n 秒）后的那个状态
如下图
Why
为什么一定要弄这样呢？我们来看看每个节点的意思，节点 ->(A: 5) -> 节点 表示前面节点做了 5 秒任务后变成了后面节点的状态。这个图就像是一个状态机，每个节点都记录了某个时间节点的状态，而边表示做任务的过程了。
这样就很好解决了“并行”的问题，如果我们想用最少的时间完成任务，那只要有分叉的地方，我们就选最长的路径就可以了。
如上面 A 所在的边是 5，D 所在的边是 8，我们应该选 8，因为走 8 这条路后，A 肯定也就完成了。而如果我们选了 5 这条路，A 是做完了，但是 D 不一定做完呀，还剩 呢。
所以现在问题变成了求新图的最长路径的问题。
最长路径
最长路径其实真的就是最短路径的镜像问题，这里还是提一下吧。
首先需要两个数组 dist 和 pred 用于存放 S 到该节点的最长距离和该节点的前一个指向它的节点（称前驱节点）。
得到拓扑排序后，对每个节点操作：
- 如果节点是 S 开始节点，那么
dist[v] = 0
pred[v] = null
- 如果节点没有入度为 0，那么
dist(v) = -Infinite
pred(v) = null
- 剩下的情况就是求最长路径了，这个就用一下动态规划方程就好了
dist(v) = max(dist(u) + length(u -> v))
pred(v) = u
这个算法的时间复杂度是
网友评论