关键路径怎么求？求详解。
关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。
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)计算是软考中的必考题，是一个重点也是一个难点。在中级和高级考试中都会以选择题或简答题型出现，只要撑握了关键路径计算方法，一般这部分得分还是比较有把握的
关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。
首先你应该找到最早完成跟最迟完成的时间，然后剪一下就可以了
符竹心3261 :答：e[i]=ve[j]; l[i]=vl[k]-dut<vj,vk> 若 e[i]=l[i]即为关键活动。由关键活动组成的路径即关键路径 v1最早发生时间:ve[1]=ve[0]+a1=0+5=5;v2最早发生时间:ve[2]=ve[0]+a2=0+6=6;v3最早发生时间:有两条路v0->v1->v3,路径长度为5+3=8；v0->v2->3, 路径长度为6...
符竹心3261 :答：关键路径的计算方法如下：（1） 输入e条弧<j,k>，建立AOE网的存储结构；（2） 从源点v1出发，令ve(1)=0，求 ve(j) ,2<=j<=n；（3） 从汇点vn出发，令vl(n)=ve(n)，求 vl(i), 1<=i<=n-1；（4） 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开...
符竹心3261 :答：根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改...
符竹心3261 :答：求关键路径1.首先求关键节点求关键节点的方法，若求关键节点，则须知该节点最早发生的时间V(i)e和最晚发生的时间V(i)l最早发生时间V(i)e=max{V(j)e+dut(j,i)}其中dut(j,i)表示从节点j到节点i代价即活动的代价；例如V(1)e=0;V(1)表示1结点V(2)e=max{V(1)e+dut(1,2)}=0+6=...
符竹心3261 :答：以一个具体的例子来说明如何求解AOE网中的关键路径：1. 首先计算每个事件的最早开始时间ve，即从起始顶点到该事件的最长路径上的时间。2. 接着计算每个事件的最晚开始时间vl，即从终止顶点到该事件的最短路径上的时间。3. 使用红色标记ve，黑色标记vl，以便在图中清晰区分。4. 对于每个活动，计算其...
符竹心3261 :答：最早发生时间和最迟发生时间相同的结点即为关键路径上的节点。例如节点4有两个前驱结点（节点2和3），节点2到节点4的最早发生时间是a1+a3也就是8，节点3到节点4的最早发生时间是a2+a4也就是12，因为12>8，所以节点4的最早发生时间是12。
符竹心3261 :答：1.何为节点计算法？节点计算法是一种项目管理中常用的工具，可以帮助我们分析项目进度、找到关键路径，对项目进行有效的管理和控制。2.节点计算法有哪些步骤？节点计算法的主要步骤包括：确定任务及其先后关系；绘制活动网络图；定每个活动的持续时间；计算最早开始时间和最晚开始时间；计算最早完成时间和最晚...
符竹心3261 :答：方法：1、最长线路法（也叫关键路径法）在关键线路法（CPM）中，线路上所有工作的持续时间总和称为总持续时间。在所有线路中总持续时间最长的线路即为关键线路。此法确定关键线路的步骤如下：1.计算各个线路的总持续时间 寻找从始节点①至终节点⑥的所有线路并求其总历时 ①②④⑥ t=1+2+5=8 ①...
符竹心3261 :答：求上图中VOE网中的关键路径：1，求事件的最早开始时间ve=max{顶点+边}和最晚开始时间vl=min{尾-边} 2，为了后面更好的求活动的最早开始时间和最晚开始时间，将ve和vl都在图中标识出来，ve用红笔，vl用黑笔 3，求活动的最早最晚开始时间，最早e={ve顶}，最晚l={vl尾-边} 其中关键活动就...
符竹心3261 :答：楼上的结果有误，以下是我自己写的过程。1）关键路径为C-G-J-L 项目的工期即关键路径长度，为8+7+7+4=26 2）由题意，ESA=ESB=0 活动A：ESA=0，EFA=ESA+D=0+6=6（注：式中的D表示相应活动持续时间，下同，我没有逐个编号）活动B：ESB=0，EFB=ESB+D=0+8=8 活动E：ESE=EFB=8，...
