什么时候用关键路径算法

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

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

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天。

packagegraph;
importjava.util.*;
publicclassGrph_CriticalPath
{
Graph_AdjListadjList;
Stack<Integer>T=newStack<Integer>();
intve[];
intvl[];
finalintmax=10000;

publicGrph_CriticalPath(Graph_AdjListadjList)//图的存储结构是用的邻接表
{
this.adjList=adjList;
intlength=adjList.vetexValue.length;
ve=newint[length];
vl=newint[length];
for(inti=0;i<length;i++)
{
ve[i]=0;
vl[i]=max;
}
}

publicvoidgetCriticalPath()
{
topologicalOrder();

intt=T.pop();
T.push(t);
vl[t]=ve[t];
while(!T.isEmpty())
{
intj=T.pop();
for(Graph_AdjList.ArcNodep=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j]=vl[k]-p.weight;
}
}
}
for(inti=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNodep=adjList.vetex[i].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
intee=ve[i];
intel=vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+"");
}

}
}
}

publicvoidtopologicalOrder()
{
Stack<Integer>S=newStack<Integer>();
S.push(0);
intcount=0;
while(!S.isEmpty())
{
intj=S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNodep=null;
for(p=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=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;
}
}

publicvoidprint()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+"");
}
}

publicvoidprintVel()
{
System.out.println();
for(inti=0;i<ve.length;i++)
{
System.out.print(ve[i]+"");
}
System.out.println();
for(inti=0;i<vl.length;i++)
{
System.out.print(vl[i]+"");
}
}


}

转自：http://blog.csdn.net/pigli/article/details/5777048

㈡ pmp如何计算关键路径

pmp计算关键路径的方法如下：

关键路径法（Critical Path Method）是一种用来预测总体项目历时的项目源网络分析技术。所谓“关键路径”，是指当我们完成了项目进计划后，在项目的网络图上，存在着若干条从项目启动到项目结束之间的路径，但是对其中一条（严格的来说，可能存在一条以上）路径上来说。

所谓正推法就是从项目的第一个活动到最后一个活动跟踪全部活动的先后关系，计知算出每个活动的最早开始时间（ES）和最早结束时间（EF）。

所谓倒道推法则是从最后一个活动开始向前追溯到第一个活动，计算出每个活动的最晚开始时间（LS）和最晚结束时间（LF）。

PMP作为项目管理资格认证考试，已在国际上树立了其权威性：

1、PMP为美国培养了一大批项目管理专业人才，项目管理职业已成为美国的“黄金职业”。在中国许多媒体已把PMP称为继MBA，MPA之后的三大金字招牌之一；

2、PMP认证已成为了一个国际性的认证标准，用英语、德语、法语、日语、韩语、西班牙语、葡萄牙语和中文等九种语言进行认证考试；

3、到目前为止，全球有80多万名PMP，中国大陆地区获得“PMP”头衔的已有18万多人，并逐年增长；

4、各国纷纷效仿美国的项目管理认证制度，推动了世界项目管理的发展。

㈢ cpm是什么意思

CPM在项目计划管理方法中代表的是什么意思?你们可曾接触过?下面是我给大家整理的cpm是什么意思，供大家参阅!

cpm是什么意思

关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接，从而能够计算项目的工期、各个活动时间特点(最早最晚时间、时差)等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。关键路径法是现代项目管理中最重要的一种分析工具。

CPM关键路径法应用

在60年代初期，PERT的发展比较迅速，据统计，到1964年，关于PERT的参考书目和论文达到了1000多种。到1961年，各种基于PERT的类似的方法出现，如PERT/Cost,PERT-RAMPS(Resource Allocation & Multi-Project Schele)，MAPS，SCANS，TOPS，PEP，TRACE，LESS和PAR等。其中PEP法是将甘特图的活动赋以逻辑关系，这是计划软件一般采用的一种图形输出方法。1962年的时候，时任美国国防部长MacNamara在起草一项法令时，指出计划评审法和关键路径法同时并存的局面容易引起混淆，以后国防部的所有部门一律使用计划评审法(PERT)，这在当时对于关键路径法的提倡者是一个重大打击，不过在随后的发展中，关键路径法(CPM)逐渐占了优势，真正使用计划评审法的其实已经很少。而且即使是在当时，很多所谓的计划评审法(PERT)，其实质其实是关键路径法(CPM)。如美国航空局(NASA)当时使用的NASA-PERT，实际就是关键路径法(CPM)。

无论是关键路径法(CPM)还是计划评审法(PERT)，最初使用的表示方法都是箭线法(ADM)，在之后很长的一段时间箭线法(ADM)都是人们主要使用的方法，直到70年代以后，前导图(PDM)才开始逐渐流行起来，但是箭线法(ADM)仍然使用极为广泛。在90年代以后，美国Primavera公司开发出其Windows版本的计划管理软件时，只采用前导图(PDM)作为其计算平台，从根本上改变了这一局面，从此以后，前导图(PDM)成了人们主要使用的方法，而箭线图(ADM)则很少使用。

CPM关键路径法时间计算

在进行计算时，箭线图和前导图的计算过程有所不同。

正推法

箭线图(ADM)的计算一般有正推法(Forward Pass)和逆推法(Backward Pass)两种，正推法用于计算活动和节点的最早时间，其算法如下：

⒈设置箭线图(ADM)中的第一个节点的时间，如设置为1。

⒊令活动最早开始时间等于其开始节点的最早时间。

⒋在选择的活动的最早开始时间上加上其工期，就是其最早结束时间。

⒌比较此活动的最早结束时间和此活动结束节点的最早时间。如果结束节点还没有设置时间，则此活动的最早结束时间就是该结束节点的最早时间;如果活动的结束时间比结束节点的最早时间大，则取此活动的最早结束时间作为节点的最早时间;如果此活动的最早结束时间小于其结束节点的最早时间，则保留此节点时间作为其最早时间。

⒍检查是否还有其它活动开始于此节点，如果有，则回到步骤3进行计算;如果没有，则进入下一个节点的计算，并回到步骤3开始，直到最后一个节点。

逆推法

活动和节点的最迟时间采用逆推法(Backward Pass)计算，逆推法(Backward Pass)一般从项目的最后一个活动开始计算，直到计算到第一个节点的时间为止，在逆推法的计算中，首先令最后一个节点的最迟时间等于其最早时间，然后开始计算，具体的计算步骤如下所示：

⒈设置最后一个节点的最迟时间，令其等于正推法计算出的最早时间。

⒉选择一个以此节点为结束节点的活动进行计算。

⒊令此活动的最迟结束时间等于此节点的最迟时间。

⒋从此活动的最迟结束时间中减去其工期，得到其最迟开始时间。

⒌比较此活动的最迟开始时间和其开始节点的最迟时间，如果开始节点还没有设置最迟时间，则将活动的最迟开始时间设置为此节点的最迟时间，如果活动的最迟开始时间早于节点的最迟时间，则将此活动的最迟开始时间设置为节点的最迟时间，如果活动的最迟开始时间迟于节点的最迟时间，则保留原节点的时间作为最迟时间

⒍检查是否还有其它活动以此节点为结束节点，如果有则进入第二步计算，如果没有则进入下一个节点，然后进入第二步计算，直至最后一个节点。

⒎第一个节点的最迟时间是本项目必须要开始的时间，假设取最后一个节点的最迟时间和最早时间相等，则其值应该等于1。

㈣ 关键路径怎么算

关键路径的计算方法如下：

（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)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。

关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。

(4)什么时候用关键路径算法扩展阅读：

一、拓扑排序的执行

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

（1）选择一个入度为0的顶点并输出之；

（2）从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

二、关键路径相关术语

（1）AOE网

用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。一个AOE网的关键路径可以不止一条。

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。

表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点和唯一的出度为0的完成顶点。

（2） 活动开始的最早时间e(i)；

（3） 活动开始的最晚时间l(i)；

（4） 事件开始的最早时间ve(i)；

（5） 事件开始的最晚时间vl(i)。