长沙网站设计公司排名,西安网站制作费用,wordpress外贸网站模板,做网站实时数据用接口关键路径梳理活动的顺序仅仅是拓扑排序可以完成的功能之一#xff0c;更有价值的是估量完成整个事件的最短时间。比如生产一辆汽车#xff0c;虽然安排员工、准备原始材料是先行条件#xff0c;但是组装各种零部件是可以同时进行的#xff0c;例如制造轮子和发动机、外壳等…关键路径梳理活动的顺序仅仅是拓扑排序可以完成的功能之一更有价值的是估量完成整个事件的最短时间。比如生产一辆汽车虽然安排员工、准备原始材料是先行条件但是组装各种零部件是可以同时进行的例如制造轮子和发动机、外壳等是可以同时进行的这样可以大大减少生产时间。这种场景我们称为AOE网。在一个表示工程的带权有向图中用顶点表示事件用有向边表示活动用边上的权值表示活动的持续时间这种有向图的边表示活动的网称之为AOE网(Activity On Edge Network)。我们的目标就是在这样的AOE网中确定它的最短完成时间而具备最短时间的路径就是关键路径。把路径上各个活动所持续的时间之和称为路径长度从起点到终点具有最大长度的路径叫关键路径在关键路径上的活动叫关键活动。那么我们怎么确定一个活动是不是关键活动呢以做饭为例我们可以同时烧水、炒菜和熬粥其中烧水只需要3分钟炒菜需要10分钟熬粥需要20分钟。那么很显然至少需要20分钟才能完成全部工作也就是说在这20分钟时间里熬粥必须从一开始就进行而烧水则可以从开始进行也可以等17分钟后再进行炒菜也可以从开始进行或者最晚等10分钟后进行。这里没有空闲时间的活动就是关键活动。例如下图就是一个AOE网其中权值表示活动需要的时间以从v0-v3为例假设权值表示的时间单位为分钟可选的路径有v0-v1-v3需要8分钟或者v0-v2-v3需要12分钟。要尽快到达v3则v2必须一开始立刻启动而v1可以在最开始或者等待4分钟之后再启动所以v0-v2-v3是关键路径。按照此方式可以得到此AOE网的关键路径如下那么接下来我们只需要确认每个顶点的最早开始时间和最晚开始时间判断它们的时间差如果没有时间差就是关键路径。代码实现首先我们需要对AOE网进行拓扑排序在排序的同时还可以得到每个顶点事件的最早发生时间代码如下所示public boolean topoSort(ATGraph atGraph,int[] earlestTimeVertex,Stack stack2) { int count 0; Queue queue new LinkedList(); for (int i 0; i atGraph.getLen(); i) { if (atGraph.getVertex(i).getIn() 0) { queue.offer(atGraph.getVertex(i)); } } while (!queue.isEmpty()) { ATVertex vertex queue.poll(); System.out.print(vertex.getData() -); //将排序的数据push到stack2中 stack2.push(vertex); count; //获取第一条边 ATEdge next vertex.getNext(); while (next ! null) { //获取 ATVertex nextVertex next.getVertex(); nextVertex.setIn(nextVertex.getIn() - 1); if (nextVertex.getIn() 0) { queue.offer(nextVertex); } // 计算每个顶点可以执行的最早时间 // 获取弧尾顶点下标 int topIndex atGraph.getVertexIndex(vertex); // 获取弧头顶点下标 int index atGraph.getVertexIndex(nextVertex); // 更新当前顶点可以发生的最早时间 if (earlestTimeVertex[topIndex] next.getWeight() earlestTimeVertex[index]) { earlestTimeVertex[index] earlestTimeVertex[topIndex] next.getWeight(); } next next.getNext(); } } return count atGraph.getLen();}现在我们得到了最早发生时间并且将全部顶点按照访问的先后顺序压进了一个栈中这是为了方便进行计算最晚发生时间。从前向后计算最晚发生时间是复杂的但是反过来却很简单对于最后一个顶点它的最晚发生时间和最早发生时间一定一致而它前面的顶点就必须在此时间点之前完成。参考代码如下for (int i 0; i atGraph.getLen(); i) { // 先将最晚发生时间都设置为最长时间 latestTimeVertex[i] earlestTimeVertex[atGraph.getLen()-1];}// 从后向前更新每个顶点的最晚发生时间while (!stack2.isEmpty()){ ATVertex vertex stack2.pop(); ATEdge next vertex.getNext(); while (next!null){ ATVertex nextVertex next.getVertex(); int nextIndex atGraph.getVertexIndex(nextVertex); int index atGraph.getVertexIndex(vertex); if (latestTimeVertex[nextIndex]-next.getWeight()最后只要按照顺序比对这两个时间是否相等就可以得到完整的关键路径了完整代码如下public void criticalPath(ATGraph atGraph){ Stack stack2 new Stack(); int[] earlestTimeVertex new int[atGraph.getLen()]; int[] latestTimeVertex new int[atGraph.getLen()]; topoSort(atGraph,earlestTimeVertex,stack2); for (int i 0; i atGraph.getLen(); i) { // 先将最晚发生时间都设置为最长时间 latestTimeVertex[i] earlestTimeVertex[atGraph.getLen()-1]; } // 从后向前更新每个顶点的最晚发生时间 while (!stack2.isEmpty()){ ATVertex vertex stack2.pop(); ATEdge next vertex.getNext(); while (next!null){ ATVertex nextVertex next.getVertex(); int nextIndex atGraph.getVertexIndex(nextVertex); int index atGraph.getVertexIndex(vertex); if (latestTimeVertex[nextIndex]-next.getWeight() vertex atGraph.getVertex(i); ATEdge next vertex.getNext(); while (next!null){ ATVertex nextVertex next.getVertex(); int nextIndex atGraph.getVertexIndex(nextVertex); lte latestTimeVertex[nextIndex]-next.getWeight(); ete earlestTimeVertex[i]; if (etelte){ System.out.println(路径atGraph.getVertex(i).getData()-atGraph.getVertex(nextIndex).getData()
