复杂网络最长路径算法，有偿求大家帮助。
根据复杂网络现有最短路径的几种算法，写出求最长路径的算法，先思路再具体算法。
问题解决后有更多酬谢。求各位专业人士帮助
对于一幅加权有向无环图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的起始顶点的最长路径。
源码实现：
/**
* % 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));
}
}
1。 肯定不能用dijkstra算法，这是因为，Dijkstra算法的大致思想是每次选择距离源点最近的结点加 入，然后更新其它结点到源点的距离，直到所有点都被加入为止。当每次选择最短的路改为每次选择最长路的时候，出现了一个问题，那就是不能保证现在加入的结 点以后是否会被更新而使得到源点的距离变得更长，而这个点一旦被选中将不再会被更新。例如这次加入结点u，最长路为10，下次有可能加入一个结点v，使得 u通过v到源点的距离大于10，但由于u在之前已经被加入到集合中，无法再更新，导致结果是不正确的。
如果取反用dijkstra求最短路径呢，记住，dijkstra不能计算有负边的情况。。。
2.
可 以用 Bellman-Ford 算法求最长路径，只要把图中的边权改为原来的相反数即可。也可以用Floyd-Warshall 算法求每对节点之间的最长路经，因为最长路径也满足最优子结构性质，而Floyd算法的实质就是动态规划。但是，如果图中含有回路，Floyd算法并不能 判断出其中含有回路，且会求出一个错误的解；而Bellman-Ford算法则可以判断出图中是否含有回路。
- 如果是有向无环图，先拓扑排序，再用动态规划求解。
用广度优先搜索算法不好吗？
第一次回答有点扯远了，是最长路的应用，与问题关联性不强。删除了
把路径转换为负数，然后来求最短路的想法是对的，也是比较好的，但是最短路径只能用spfa或者是Floyd不能用dijk（因为dijk使用贪心写的，所以会有问题），而spfa在判环的时候很灵活，再建图的时候也很方便，所以一般都是用spfa求最短路，最后输出绝对值就行了