一、定义
最长路径算法类似于基于拓扑排序的最短路径算法。本文只针对加权有向无环图讨论。
二、基本思想
对于一幅加权有向无环图G，指定源点s，求s到其余各个顶点的最长路径，相当于复制原始加权有向无环图得到一个副本，并将副本中的所有边的权重变为负值。这样，副本中的最短路径就是原图G中的最长路径。
三、算法实现
最长路径算法的实现步骤如下：
- 初始时，定义如下数据结构
distTo[i]：保存顶点i到源点s的当前已知最长路径，初始时为负无穷大；
edgeTo[v]：保存各个顶点在最长路径上的父路径，如edgeTo[v]表示源点s->v的最长路径上的最后一条路径。 - 对于加权有向无环图（DAG），进行拓扑排序，得到一个拓扑序列；
- 依照拓扑序列，依次对顶点v进行逆松弛操作。
即如果PATH(s,w) < PATH(s,v) + PATH(v,w)，则更新PATH(s,w) = PATH(s,v) + PATH(v,w)
算法源码：
public class AcyclicLP {
// distTo[v]保存顶点v到源点s的最长路径，初始时，distTo[s]=0，其它为负无穷大
private double[] distTo;
// edgeTo[v]保存指向顶点v的最长路径，即s->v的路径上的最后一条路径
private DirectedEdge[] edgeTo;
public AcyclicLP(EdgeWeightedDigraph G, int s) {
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.NEGATIVE_INFINITY;
distTo[s] = 0.0;
// relax vertices in toplogical order
Topological topological = new Topological(G);
if (!topological.hasOrder())
throw new IllegalArgumentException("Digraph is not acyclic.");
for (int v : topological.order()) {
for (DirectedEdge e : G.adj(v))
aRelax(e);
}
}
private void aRelax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] < distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] > Double.NEGATIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}
四、性能分析
时间复杂度：O(E+V)
五、实际应用
基于拓扑排序的最长路径算法可以解决：
优先级限制下的并行调度问题
具体步骤：
首先，将问题转化为一幅加权有向无环图，然后利用基于拓扑排序的最长路径算法求解。
- 对于有V个任务的优先级调度问题，创建2*V+2个顶点（1个起点s，1个终点t，每个任务2个顶点v和v'）；
- 每个任务添加一条从v->v'的边，权重为任务所需时间；
- 对于每条优先级限制v->w，添加一条从v的结束顶点v'到w的起始顶点的权重为0的边，即v'->w；
- 每个任务v还要添加：s->v的权重为0的边、v'->t的权重为0的边。
经过上述处理后，每个任务v的开始时间就是从起点s到v的起始顶点的最长路径。
5-1 基于拓扑排序的调度问题求解
源码实现：
/**
* % java CPM < jobsPC.txt
* job start finish
* --------------------
* 0 0.0 41.0
* 1 41.0 92.0
* 2 123.0 173.0
* 3 91.0 127.0
* 4 70.0 108.0
* 5 0.0 45.0
* 6 70.0 91.0
* 7 41.0 73.0
* 8 91.0 123.0
* 9 41.0 70.0
* Finish time: 173.0
**/
public class CPM {
private CPM() { }
public static void main(String[] args) {
// 任务数
int n = StdIn.readInt();
// 起点和终点
int source = 2*n;
int sink = 2*n + 1;
// 构建拓扑图
EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*n + 2);
for (int i = 0; i < n; i++) {
double duration = StdIn.readDouble(); //权重
G.addEdge(new DirectedEdge(source, i, 0.0));
G.addEdge(new DirectedEdge(i+n, sink, 0.0));
G.addEdge(new DirectedEdge(i, i+n, duration));
int m = StdIn.readInt();
for (int j = 0; j < m; j++) {
int precedent = StdIn.readInt();
G.addEdge(new DirectedEdge(n+i, precedent, 0.0));
}
}
// compute longest path
AcyclicLP lp = new AcyclicLP(G, source);
// print results
StdOut.println(" job start finish");
StdOut.println("--------------------");
for (int i = 0; i < n; i++) {
StdOut.printf("%4d %7.1f %7.1f\n", i, lp.distTo(i), lp.distTo(i+n));
}
StdOut.printf("Finish time: %7.1f\n", lp.distTo(sink));
}
}
