关键路径怎么求？求详解。

关键路径怎么算~

关键路径是项目管理中进度控制的一个术语。关键路径法的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)计算是软考中的必考题，是一个重点也是一个难点。在中级和高级考试中都会以选择题或简答题型出现，只要撑握了关键路径计算方法，一般这部分得分还是比较有把握的

关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。

首先你应该找到最早完成跟最迟完成的时间，然后剪一下就可以了

---

龙岗区17210119714： 什么是关键路径?关键路径如何求解? - ？
蒲裘利舒：[答案] 在项目管理中,关键路径是指网络终端元素的元素的序列,该序列具有最长的总工期并决定了整个项目的最短完成时间.关键路径的工期决定了整个项目的工期.任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间(例...

龙岗区17210119714： 关键路径怎么算 - ？
蒲裘利舒：[答案] 关键路径(critical path)简要介绍关键路径是项目管理中进度控制的一个术语.在项目的网络图中,从项目开始到项目完成有许多条路径可以走,就像从798艺术区到北京大学一样(如图1).如果20个人同时从798艺术区出发,每...

龙岗区17210119714： 关键线路确定的算法步骤是怎样的? - ？
蒲裘利舒：[答案] 第1步,拓扑排序,确定顶点的先后次序 第2步,按顶点先后顺序从前向后递推,求出结点的最早开工时间 第3步,从后向前... 第5步,计算活动的松弛时间,为0的就是关键活动,从始点到终点的所有关键活动就是关键路径

龙岗区17210119714： 关于求关键路径的一句话:一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续...关于求关键路径的一句话:一个事件的最迟开... - ？
蒲裘利舒：[答案] 因为你无法保证,这两个事件同时存在的路线就是第一个世界的最长路径

龙岗区17210119714： 图的关键路径 - ？
蒲裘利舒： int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间 int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间 int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间 edgenode *p; ...

龙岗区17210119714： 请解释一下关键路径! - ？
蒲裘利舒： 你理解反了,关键路径是指决定系统活动消耗所需时间长度的那条路径.也就是说,它是所有路径中消耗最长时间的那条路径.根据木桶原理,减少关键路径所消耗的时间,整个系统活动所消耗的时间也随之降低,反之亦然.所以才称之为关键路径

龙岗区17210119714： 项目管理名词解释1、甘特图2、工作包3、关键路径法 - ？
蒲裘利舒：[答案] 甘特图(Gantt chart )又叫横道图、条状图(Bar chart).它是以图示的方式通过活动列表和时间刻度形象地表示出任何特定... 只报告该工作包是否完成.通过这种定期检查的方法,可以控制项目的变化. 关键路径法(Critical Path Method,CPM)是一...

龙岗区17210119714： pert图怎么画 - ？
蒲裘利舒：[答案] 信息工程项目应用网络计划技术的步骤如下:①绘制网络图;②网络计划计算;③求关键路径;④计算完工期及其概率;⑤网络计划优化. 步骤1:绘制ERP项目网络图 本文主要以某公司(中小型企业)ERP项目建设为例,讲述网络计划技术在信息...

龙岗区17210119714： 怎么实现关键路径算法动态演示 - ？
蒲裘利舒： 短路径算简单由起点层层向外寻找终点种算效率低几十节点图没问题 另外种思路比较适合少量节点图由计算机预先计算每节点至其节点短路径存储数据库短路径数据表至于两条线路走三条线路走问题解决

龙岗区17210119714： 数据结构,为什么?详解! 下面( )方法可以判断出一个有向图是否有环. - ？
蒲裘利舒：[选项] A. 深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径