关键路径算法

A. 关键路径法的公式计算

上面介绍了活动的最早和最迟时间的计算方法，以上的过程可以用比较简单的公式来表达。 上面所讲述的方法，我们一般称为节点计算法，节点和活动的最早时间按照正推法进行计算，起点节点未规定时间时，我们取其时间为1，即
ETi=1（i=1）
对于任意一个节点，如果其之前只有一条活动时，则其最早时间按照下式计算，
ETj= ETi+Di-j
如果该节点之前有多条活动时，则其最早时间按照下式计算，ETj= max{ETi+Di-j}
其中Di-j为活动i-j的工期
对于活动的最早时间，最早开始时间为：
ESi-j=ETi
最早结束时间为
EFi-j= ESi-j+ Di-j
计划的总工期
T=ETn-1
节点和活动的最迟时间以逆推法计算，计算时，首先令最后一个节点的最迟时间等于其最早时间，即
LTn=ETn
对于其之后只有一条活动的节点，最迟时间如下式所示
LTi=LTj-Di-j
对于其之后有多条活动的节点，最迟时间如下式所示
LTj=min{ LTj-Di-j}
工作i-j的最迟完成时间以下式计算，
LFi-j=LTj
最迟开始时间为
LSi-j=LFj- Di-j 以上的算法是节点计算法，另外，也可以采用一种叫做工作计算法的方法进行活动时间的计算，具体如下。
对于最早时间，采用正推法计算。在没有指定节点的开始时间时，则起点开始活动的最早开始时间定为1，即
ESi-j=1
当工作i-j只有一条紧前工作h-i时，其最早开始时间按如下公式计算ESi-j=ESh-i+ Dh-i
当工作i-j有多条紧前工作时，其最早开始时间按照以下公式计算
ESi-j=max {ESh-j+ Dh-i}
工作i-j的最早完成时间按照下式计算
EFi-j=ESi-j+ Di-j
网络计划的计算工期按照下式确定
T=max {EFi-n}-1
活动的最迟结束时间和最迟开始时间需要采用逆推法计算。
以终点节点为箭头节点的活动的最迟完成时间按照网络计划的工期确定，即
LFi-j=T+1
其它活动的最迟开始时间按照下式计算
LFi-j=min {LFj-k- Dj-k}
活动的最迟开始时间以下式确定
LSi-j=LFi-j- Di-j
对于总时差和自由时差可以采用如下的公式计算。
总时差可以按照下式计算：
TFi-j= LSi-j- ESi-j
或者
TFi-j= LFi-j- EFi-j
当工作i-j有紧后工作j-k时，自由时差可以按照下式计算：
FFi-j=ESi-k- ESi-j- Di-j
或者
FFi-j=ESj-k-EFi-j
由于引入了多种逻辑关系，前导图（PDM）的时间计算和箭线图（ADM）有一些差别。除了前导图（PDM）中不存在节点最早时间和最迟时间，在箭线图（ADM）中提及的其它时间参数也都适合前导图（PDM）。 对于活动的最早开始和最早结束时间，采用正推法计算，其算法如下所示：
⒈将第一个活动的最早开始时间设置为1.
⒉在活动的最早开始时间上加上其工期，得到活动的最早结束时间。
⒊根据该活动与后置活动的逻辑关系，计算后置活动应该的最早开始时间，并与其已有的最早开始时间对比，如果其后置活动还没有设置最早开始时间，则将此时间设为其最早开始时间，如果此时间早于其后置活动已有的最早开始时间，则保留后置活动的原有最早开始时间，如果此时间迟于其后置活动已有的最早开始时间，则将此时间设置为后置活动的最迟开始时间。
⒋重复步骤2和3，直到所有活动的时间被计算完为止。
对于以上所示的最早时间的计算过程，可以以公式的形式表示如下：
当活动间的逻辑关系为SS，则计算如下
ESj=max{ ESi+ STS}
当活动间的逻辑关系为FS，则计算如下
ESj= max{ESi+ Di+ FTS}
当活动间的逻辑关系为FF，计算如下
ESj= max{ESi+ Di- Dj+FTF}
当活动间的逻辑关系为SF，计算如下
ESj=max{ ESi- Dj+STF}
在计算出各个活动的最早开始和结束时间之后，就可以计算活动的自由时差，在计算前导图（PDM）的自由时差时应注意，由于引入了多种逻辑关系，并且活动间可以存在延时，所以其计算方法与箭线图（ADM）的计算方法不一样。 对于前导图（PDM）的活动间，除了延时还可以存在时间间隔（LAG），一般可以按照下面的方式计算。
当活动间的逻辑关系为SS，则计算如下
LAGi-j= ESj- ESi- STS
当活动间的逻辑关系为FS，则计算如下
LAGi-j= ESj- EFi- FTS
当活动间的逻辑关系为FF，计算如下
LAGi-j= EFj- EFi- FTF
当活动间的逻辑关系为SF，计算如下
LAGi-j= EFj- ESi- STF
则对于任意一个活动，其自由时差为
FFi=min{ LAGi-j}
最后一个活动的自由时差为0.
对于总时差，终点节点的总时差为0，对于其它任意一个节点，总时差按照下式进行计算
TFi=min{TFj+ LAGi-j}
对于任意一个活动的最晚开始时间可以由其最早开始时间加上总时差得到，同样，其最晚开始时间可以由最早结束时间加上其总时差得到，公式表示如下
LSi=ESi+TFi
LFi=EFi+TFi

B. pmp如何计算关键路径

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

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

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

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

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

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

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

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

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

C. 关键路径怎么求求详解。

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

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

D. 怎么实现关键路径算法动态演示

短路径算简单由起点层层向外寻找终点种算效率低几十节点图没问题

另外种思路比较适合少量节点图由计算机预先计算每节点至其节点短路径存储数据库短路径数据表至于两条线路走三条线路走问题解决

E. 如何计算关键路径

并行的活动：最早结束时间大者，在关键路径。以网上一图举例。

A-->B/C并列，其中C活动最早结束时间（EalyFinish）为第13天，大于7，所以C在关键路径上。

A-->C-->D/E,23>18,同上

A-->C-->D-->G,同上

A-->C-->D-->G-->H，同上