根据复杂网络现有最短路径的几种算法,写出求最长路径的算法,先思路再具体算法。
问题解决后有更多酬谢。求各位专业人士帮助
复杂网络最长路径算法,有偿求大家帮助。
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
4条回答 默认 最新
- ilmss 2022-08-12 13:51关注
获得1.00元问题酬金 对于一幅加权有向无环图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)); } }
解决 无用评论 打赏 举报
悬赏问题
- ¥15 Todesk 远程写代码 anaconda jupyter python3
- ¥15 我的R语言提示去除连锁不平衡时clump_data报错,图片以下所示,卡了好几天了,苦恼不知道如何解决,有人帮我看看怎么解决吗?
- ¥15 在获取boss直聘的聊天的时候只能获取到前40条聊天数据
- ¥20 关于URL获取的参数,无法执行二选一查询
- ¥15 液位控制,当液位超过高限时常开触点59闭合,直到液位低于低限时,断开
- ¥15 marlin编译错误,如何解决?
- ¥15 有偿四位数,节约算法和扫描算法
- ¥15 VUE项目怎么运行,系统打不开
- ¥50 pointpillars等目标检测算法怎么融合注意力机制
- ¥20 Vs code Mac系统 PHP Debug调试环境配置