关键路径怎么求？求详解。
关键路径是项目管理中进度控制的一个术语。关键路径法的4个关键步骤：
（1） 关键路径是项目网络图中最长的路径，他决定了项目的总耗时时间；
（2） 项目经理必须把注意力集中在那些优先等级较高的任务，确保他们准时完成，关键路径上任何活动的推迟都将导致整个项目推迟；
（3） 项关键路径要时间，向非关键路径要资源；
（4） 调整进度，平衡资源。
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。
在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。
关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。
1． 什么是拓扑排序？
举个例子先：一个软件专业的学生学习一系列的课程，其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边表示先决条件。若课程i是课程j的先决条件，则图中有弧<i,j>。若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列，必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前，若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列，称之为拓扑序列。
2． 如何实现拓扑排序？
很简单，两个步骤：
1． 在有向图中选一个没有前驱的顶点且输出。
2． 从图中删除该顶点和以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
3． 什么是关键路径？
例子开头仍然，图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2......，v9，每个事件表示在它之前的活动一完成，在它之后的活动可以开始。如v1表示整个工程的开始，v9表示整个工程结束，v5表示a4和a5已完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天。
由于整个工程只有一个开始点和一个完成点，故在正常情况(无环)下，网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
那么该工程待研究的问题是：1.完成整项工程至少需要多少时间？2.哪些活动是影响工程进度的关键？
由于在AOE-网中有些活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。
假设开始点是v1，从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候，也即是l(i)=e(i)的活动，我们称其为关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。
因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的功效，缩短整个工期。
4． 如何实现关键路径？
由上面的分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系
e(i) = ve(j)
l(i) = vl(k) - dut(<j,k>)
求解ve(j)和vl(j)需分两个步进行：
1） 从ve(0)=0开始向前推进求得ve(j)
Ve(j) = Max{ve(i) + dut(<i,j>) };<i,j>属于T，j=1,2...,n-1
其中T是所有以第j个顶点为头的弧的集合。
2） 从vl(n-1) = ve(n-1)起向后推进求得vl(j)
vl(i) = Min{vl(j) - dut(<i,j>};<i,j>属于S，i=n-2,...,0
其中，S是所有以第i个顶点为尾的弧的集合。
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说，ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)必须在Vj的所有后继的最迟发生时间求得之后才能确定。因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
具体算法描述如下：
1． 输入e条弧<j,k>，建立AOE-网的存储结构。
2． 拓扑排序，并求得ve[]。从源点V0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。
3． 拓扑逆序，求得vl[]。从汇点Vn出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4． 求得关键路径。根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。
为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中，增设一个栈，以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列。
package graph;
import java.util.*;
public class Grph_CriticalPath
{
Graph_AdjList adjList;
Stack<Integer> T = new Stack<Integer>();
int ve[];
int vl[];
final int max = 10000;
public Grph_CriticalPath(Graph_AdjList adjList) //图的存储结构是用的邻接表
{
this.adjList = adjList;
int length = adjList.vetexValue.length;
ve = new int[length];
vl = new int[length];
for(int i=0;i<length;i++)
{
ve[i] = 0;
vl[i] = max;
}
}
public void getCriticalPath()
{
topologicalOrder();
int t = T.pop();
T.push(t);
vl[t] = ve[t];
while(!T.isEmpty())
{
int j = T.pop();
for(Graph_AdjList.ArcNode p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j] = vl[k]-p.weight;
}
}
}
for(int i=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNode p = adjList.vetex[i].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
int ee = ve[i];
int el = vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+" ");
}
}
}
}
public void topologicalOrder()
{
Stack<Integer> S = new Stack<Integer>();
S.push(0);
int count = 0;
while(!S.isEmpty())
{
int j = S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNode p = null;
for(p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weight>ve[k])
{
ve[k] = ve[j]+p.weight;
}
}
}
if(count<adjList.vetexValue.length)
{
System.out.println("图中存在环路！");
return;
}
}
public void print()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+" ");
}
}
public void printVel()
{
System.out.println();
for(int i=0;i<ve.length;i++)
{
System.out.print(ve[i]+" ");
}
System.out.println();
for(int i=0;i<vl.length;i++)
{
System.out.print(vl[i]+" ");
}
}
}
转自：http://blog.csdn.net/pigli/article/details/5777048
1、下载360安全卫士，打开界面，然后右下角人工服务——热门工具——搜索（重装系统）打开之后点击重装系统，自动下重装。
2、打开人工服务——360专家（免费）——通过预约专家——微信预约专家——在预约的时间会通知你打开电脑然后以远程服务的方法来帮你重装。
关键路径法(CPM)计算是软考中的必考题，是一个重点也是一个难点。在中级和高级考试中都会以选择题或简答题型出现，只要撑握了关键路径计算方法，一般这部分得分还是比较有把握的
关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。
首先你应该找到最早完成跟最迟完成的时间，然后剪一下就可以了
数据结构关键路径的计算公式是什么?
答：最早开始时间等于当前边起始结点的最早发生时间。最晚开始时间等于当前边指向结点的最迟发生时间-当前边的权值。最早发生时间和最迟发生时间相同的结点即为关键路径上的节点。例如节点4有两个前驱结点（节点2和3），节点2到...
pmp如何计算关键路径
答：pmp计算关键路径的方法如下：关键路径法（Critical Path Method）是一种用来预测总体项目历时的项目源网络分析技术。所谓“关键路径”，是指当我们完成了项目进计划后，在项目的网络图上，存在着若干条从项目启动到项目结束之间...
求关键路径的简单方法
答：首先要知道什么是关键路径，关键路径是项目计划中最长的一套路径，通俗点说因为关键路径最长，所以只有保证它做完了，才能保证项目做完了，所以说它最“关键”。关键路径法是在进度计划编制中，估算项目最短完工工期，确定逻辑...
数据结构假设一个工程的进度计划用AOE网题,
答：关键路径的算法思想：1>从ve[0]=0开始利用递推公式求出其余顶点的最早发生时间ve[j]ve[j]=Max{ve[i]+dut} (i=0,1,2,….n-1 j=1,2,…n-1 <vj,vk>∈E )即从源点开始按拓扑有序求各顶点的最早发生...
关键路径长度怎么计算?
答：楼上的结果有误，以下是我自己写的过程。1）关键路径为C-G-J-L 项目的工期即关键路径长度，为8+7+7+4=26 2）由题意，ESA=ESB=0 活动A：ESA=0，EFA=ESA+D=0+6=6（注：式中的D表示相应活动持续时间，下同...
关键路径法的公式计算
答：上面介绍了活动的最早和最迟时间的计算方法，以上的过程可以用比较简单的公式来表达。 上面所讲述的方法，我们一般称为节点计算法，节点和活动的最早时间按照正推法进行计算，起点节点未规定时间时，我们取其时间为1，即ETi=1...
在双代号网络图中怎样根据时间参数确定关键工作和关键线路?
答：方法较多，比较常见是的是最长路径法。方法：1、最长线路法（也叫关键路径法）在关键线路法（CPM）中，线路上所有工作的持续时间总和称为总持续时间。在所有线路中总持续时间最长的线路即为关键线路。此法确定关键线路的步骤...
什么是关键路径
答：算法分析：1、求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径。2、只有缩短关键活动的工期才有可能缩短工期。3、若一个关键活动不在所有的关键路径上，减少它并不能减少工期。4、只有在不改变关键路径的前提...
如何识别项目关键路径
答：如何识别项目关键路径 对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径(Critical Path)，组成关键路径的活动称为关键活动。其通常做法是：1) 将项目中的各项...
《数据结构》关键路径问题【高手进】
答：回答：AOE网(Activity On Edge)即边表示活动的网,是一个带权的有向无环图,其中顶点表示事件(Event),每个事件表示在它之前的活动已经完成,在它之后的活动可以开始,弧表示活动,权表示活动持续的时间。AOE网可用来估算工程的完...
