关键路径算法

‘壹’ 怎么实现关键路径算法动态演示

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

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

‘贰’ 关键路径法的公式计算

上面介绍了活动的最早和最迟时间的计算方法，以上的过程可以用比较简单的公式来表达。 上面所讲述的方法，我们一般称为节点计算法，节点和活动的最早时间按照正推法进行计算，起点节点未规定时间时，我们取其时间为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

‘叁’ 关键路径法的时间计算

在进行计算时，箭线图和前导图的计算过程有所不同。 箭线图（ADM）的计算一般有正推法（Forward Pass）和逆推法（Backward Pass）两种，正推法用于计算活动和节点的最早时间，其算法如下：
⒈设置箭线图（ADM）中的第一个节点的时间，如设置为1。
⒉选择一个开始于第一个节点的活动开始进行计算。
⒊令活动最早开始时间等于其开始节点的最早时间。
⒋在选择的活动的最早开始时间上加上其工期，就是其最早结束时间。
⒌比较此活动的最早结束时间和此活动结束节点的最早时间。如果结束节点还没有设置时间，则此活动的最早结束时间就是该结束节点的最早时间；如果活动的结束时间比结束节点的最早时间大，则取此活动的最早结束时间作为节点的最早时间；如果此活动的最早结束时间小于其结束节点的最早时间，则保留此节点时间作为其最早时间。
⒍检查是否还有其它活动开始于此节点，如果有，则回到步骤3进行计算；如果没有，则进入下一个节点的计算，并回到步骤3开始，直到最后一个节点。 活动和节点的最迟时间采用逆推法（Backward Pass）计算，逆推法（Backward Pass）一般从项目的最后一个活动开始计算，直到计算到第一个节点的时间为止，在逆推法的计算中，首先令最后一个节点的最迟时间等于其最早时间，然后开始计算，具体的计算步骤如下所示：
⒈设置最后一个节点的最迟时间，令其等于正推法计算出的最早时间。
⒉选择一个以此节点为结束节点的活动进行计算。
⒊令此活动的最迟结束时间等于此节点的最迟时间。
⒋从此活动的最迟结束时间中减去其工期，得到其最迟开始时间。
⒌比较此活动的最迟开始时间和其开始节点的最迟时间，如果开始节点还没有设置最迟时间，则将活动的最迟开始时间设置为此节点的最迟时间，如果活动的最迟开始时间早于节点的最迟时间，则将此活动的最迟开始时间设置为节点的最迟时间，如果活动的最迟开始时间迟于节点的最迟时间，则保留原节点的时间作为最迟时间
⒍检查是否还有其它活动以此节点为结束节点，如果有则进入第二步计算，如果没有则进入下一个节点，然后进入第二步计算，直至最后一个节点。
⒎第一个节点的最迟时间是本项目必须要开始的时间，假设取最后一个节点的最迟时间和最早时间相等，则其值应该等于1。

‘肆’ 怎么在短时间内计算出活动图中关键路径长度如下图~求解！！！

路径长度最长的路径叫做关键路径(Critical path)。应该是ABDIL

‘伍’ 关键路径怎么求求详解。

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

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

‘陆’ 关键路径怎么算

输入e条弧<j，k>，建立AOE网的存储结构；从源点v1出发，令ve(1)=0，求 ve(j)，2<=j<=n；从汇点vn出发，令vl(n)=ve(n)，求 vl(i)，1<=i<=n-1。

根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

(6)关键路径算法扩展阅读

在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。

而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。

关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。

‘柒’ 如何计算关键路径

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

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

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

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

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

‘捌’ 关键路径的算法思想是什么 怎样实现怎样进行拓扑排序

建议你去看看《数据结构》，上面说的很详细，也有标程

‘玖’ 求关键路径的程序（最好是C#的，其他的也可以）

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;

namespaceToppath
{
classProgram
{
staticvoidMain(string[]args)
{
node<char>[]Mynode={newnode<char>('A'),newnode<char>('B'),newnode<char>('C'),
newnode<char>('D'),newnode<char>('E'),newnode<char>('F'),
newnode<char>('G'),newnode<char>('H'),newnode<char>('I'),
newnode<char>('J')};
GraphAdjlist<char>xiong=newGraphAdjlist<char>(Mynode);
xiong.SetEdge(Mynode[0],Mynode[1],3);
xiong.SetEdge(Mynode[0],Mynode[2],4);
xiong.SetEdge(Mynode[1],Mynode[3],5);
xiong.SetEdge(Mynode[1],Mynode[4],6);
xiong.SetEdge(Mynode[2],Mynode[3],8);
xiong.SetEdge(Mynode[2],Mynode[5],7);
xiong.SetEdge(Mynode[3],Mynode[4],3);
xiong.SetEdge(Mynode[4],Mynode[7],4);
xiong.SetEdge(Mynode[4],Mynode[6],9);
xiong.SetEdge(Mynode[5],Mynode[7],6);
xiong.SetEdge(Mynode[7],Mynode[8],5);
xiong.SetEdge(Mynode[6],Mynode[9],2);
xiong.SetEdge(Mynode[8],Mynode[9],3);
xiong.toppath();
Console.ReadKey();
}
}
classnode<T>
{
publicTData
{get;set;}
publicnode(Ttemp)
{
Data=temp;
}
}
classvextable<T>
{
publicnode<T>Vex
{get;set;}
publicadjlistnode<T>First
{get;set;}
publicintIn
{get;set;}
publicvextable()
{
Vex=null;
First=null;
}
publicvextable(node<T>p)
{
Vex=p;
First=null;
In=0;
}
}

classadjlistnode<T>
{
publicintIndex
{get;set;}
publicadjlistnode<T>next
{get;set;}
publicintWeight
{get;set;}
publicadjlistnode(intindex)
{
Index=index;
next=null;
Weight=0;
}
publicadjlistnode()
{
Index=-1;
next=null;
Weight=0;
}
}
classGraphAdjlist<T>
{
publicvextable<T>[]vext
{get;set;}
publicint[]Visited
{get;set;}
publicvextable<T>this[intindex]
{
get{returnvext[index];}
set{vext[index]=value;}
}
publicGraphAdjlist(node<T>[]mynode)
{
vext=newvextable<T>[mynode.Length];
Visited=newint[mynode.Length];
for(inti=0;i<mynode.Length;i++)
{
vext[i]=newvextable<T>(mynode[i]);
}
}

publicintIndexofvertex(node<T>x)
{
for(inti=0;i<vext.Length;i++)
{
if(vext[i].Vex.Equals(x))
returni;
}
Console.WriteLine("nothisnode");
return-1;
}

publicvoidSetEdge(node<T>v1,node<T>v2,intv)//这个Top排序要使用的是一个有向邻接表才对
{
intiv1=Indexofvertex(v1);
intiv2=Indexofvertex(v2);
adjlistnode<T>p1=newadjlistnode<T>(iv1);
adjlistnode<T>p2=newadjlistnode<T>(iv2);
//在v1处添加v2;
p2.next=vext[iv1].First;
vext[iv1].First=p2;
p2.Weight=v;
vext[iv2].In++;//添加入度
}
publicvoidtoppath()
{
Stack<int>temp=newStack<int>();//用什么都行，但必须保持一致用于存放拓扑坐标
Stack<int>toparray=newStack<int>();//用stack最好，因为正向过去算etv，反向回来算ltv，先入后出最好
Stack<int>path=newStack<int>();//再反一次，存的就是正常的拓扑图，从头开始那种
intp=-1;intm=-1;
adjlistnode<T>q=newadjlistnode<T>();
int[]etv=newint[vext.Length];//最早点
int[]ltv=newint[vext.Length];//最晚点
intete=-1;//最早边，是判断变量不是数组用来找边的
intlte=-1;//最晚边
intk=0;
for(inti=0;i<vext.Length;i++)
{
if(vext[i].In==0)
{
temp.Push(i);//压入序号
}
}
while(toparray.Count!=vext.Length)
{
p=temp.Pop();
toparray.Push(p);
q=vext[p].First;
while(q!=null)
{
vext[q.Index].In--;//下标就用最原始的值，顺序用栈保存好就行
if(vext[q.Index].In==0)
{
temp.Push(q.Index);
}
if(etv[p]+q.Weight>etv[q.Index])//正向过去算etv,etv均初始化为0
{
etv[q.Index]=etv[p]+q.Weight;
}
q=q.next;
}
}//栈就是用来压和弹的，如果想取完还有，那就在找个栈，边取边存，不是给你拿来遍历用的
for(inti=0;i<vext.Length;i++)//找到etv的最大值拿来赋值给ltv因为这是反向回去，最大值是终点值
{
if(etv[i]>m)
{
m=etv[i];
}
}

while(toparray.Count!=0)
{
k=toparray.Pop();//由于是栈所以弹出的肯定是终点
path.Push(k);//再保存一次
q=vext[k].First;
ltv[k]=m;//将所有最晚顶点置成最大值
while(q!=null)
{
if((ltv[q.Index]-q.Weight)<ltv[k])//算ltv其实是min
{
ltv[k]=ltv[q.Index]-q.Weight;
}
q=q.next;
}
}
while(path.Count!=0)//这边我感觉还是按拓扑顺序得好，因为这样可以有序的排列顶点，不按也成反正是找边，边构成路
{
inti=path.Pop();
q=vext[i].First;
while(q!=null)
{
ete=etv[i];//边上的值，其实看etv和etl就能看到，只不过用这种方式更加形象的定位到边，并且给出权值
lte=ltv[q.Index]-q.Weight;
if(ete==lte)
{
Console.WriteLine(vext[i].Vex.Data+""+vext[q.Index].Vex.Data+""+q.Weight);
}
q=q.next;
}
}
Console.ReadKey();
}
}
}
朋友看得懂不，不懂可以加我QQ：1036433209,也许你已成为大神，就当一起学习吧

‘拾’ 关键路径算法的时间复杂度

所谓关键路径，就是从工程开始到工程结束所用时间最长的路径。这是因为，在途中的每一个阶段开始之前，都要保证此前的准备工作都已完成，要不然后续工程会无法完成，在寻找路径时，只能一条路径一条路径的比较。本题结果是