c关键路径算法
A. 什么是关键路径
在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。
求关键路径的算法分析
（1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径； （2） 只有缩短关键活动的工期才有可能缩短工期； （3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期； （4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
探寻关键路径
AOE网
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。例如： 图1
图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。
AOE 网具有的性质
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。 表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。 2)
最早发生时间和最晚发生时间的定义
可以采取如下步骤求得关键活动： A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。 Ve(k)=max{ve(j) t(<j,k>)} （ 1.1 ） j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。 如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。 表1
B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-t(<j,k>)} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。 C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j)；最晚开始时间： l(i)=vl(k)-t(<j,k>) 若某条弧满足 e(i)=l(i) ，则它是关键活动。 对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1 , a4 , a7 , a8 , a10 , a11 是关键活动。
AOE 网的关键路径
图2
这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图7.21的AOE网中有二条关键路径，(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它们的路径长度都是16 。如图2所示：
AOE网研究的问题
（1） 完成整个工程至少需要多少时间； （2） 哪些活动是影响工程的关键。 1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。
关键路径的几个术语
（1） 关键路径 从源点到汇点的路径长度最长的路径叫关键路径。 （2） 活动开始的最早时间e(i) （3） 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动。 （4） 事件开始的最早时间ve(i) （5） 事件开始的最晚时间vl(i) 设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为t(<j,k>),则 e(i)=ve(j) l(i)=vl(k)-t(<j,k>) (6_6_1) 求ve(i)和vl(j)分两步： · 从ve(1)=0开始向前递推 ve(j)=Max{ ve(i)+t(<i,j>) } (6_6_2) <i,j>T, 2<=j<=n 其中，T是所有以j为弧头的弧的集合。 · 从vl(n)=ve(n)开始向后递推 vl(i)=Min{ vl(j)-t(<i,j>) } (6_6_3) <i,j>S, 1<=i<=n-1 其中，S是所有以i为弧尾的弧的集合。 两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。 4、 求关键路径的算法 (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)的为关键活动。 求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。 Status ToplogicalSort(ALGraph G,stack &T){ FindInDegree(G,indegree); InitStack(S);count=0; ve[0..G.vexnum-1]=0; while(!StackEmpty(S)) { Pop(S,j);Push(T,j); ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; if(--indegree[k]==0) Push(S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<G.vexnum) return ERROR; else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..G.vexnum-1]=ve[0..G.vexnum-1]; while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; t=*(p->info); if(vl[k]-t<vl[j]) vl[j]=vl[k]-t; } for(j=0;j<G.vexnum;++j) for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; t=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?’*’:’’; printf(j,kt,ee,el,tag); } }
B. 如何计算关键路径
并行的活动：最早结束时间大者，在关键路径。以网上一图举例。
A-->B/C并列，其中C活动最早结束时间（EalyFinish）为第13天，大于7，所以C在关键路径上。
A-->C-->D/E,23>18,同上
A-->C-->D-->G,同上
A-->C-->D-->G-->H，同上
C. 数据结构，关键路径
答案C是正确的，首先你要知道有哪些关键路径存在，在里面有3条关键路径存在
1）bdcg
2)bdeh
3)bfh
然后逐一筛选，只有C符合要求，f是3号关键路径中的活动。d是1，2号关键路径中的活动，所以同时缩短它们的工期，可以加快进度
D. 关键路径c++代码实现
/*
AOE网研究的问题
（1） 完成整个工程至少需要多少时间；
（2） 哪些活动是影响工程的关键。
注意：该程序可以计算多条关键路径的情况，
只是输出有些不仅人意
数据文件aaa.txt的内容
A B 1
A F 3
A H 4
B C 2
F C 6
H I 4
C D 3
C G 4
I G 1
D E 5
G E 3
*/
#include<iostream>
#include<fstream>
using namespace std;
#define N 9
#define MAX 10000
int g[N][N];/*存储图,有向图,有权*/
int into[N];/*存储入度*/
int ans[N];/*存储结果序列，模拟栈*/
int ve[N];/*点的最早时间 ve[j]=Max(ve[k]+g[k][j]) */
int vl[N];/*点的最迟时间 vl[i]=Min(v[k]-g[i][k]) */
//int ee[N*N];/*边的最早时间 ee[m]=ve[i]*/
//int el[N*N];/*边的最迟时间 el[m]=vl[j]-g[i][j]*/
bool topoSort()
{
/*初始化*/
for(int i=0;i<N;i++)
{
into[i]=-1;
ans[i]=-1;
ve[i]=0;/*初始化ve*/
}
/*计算入度*/
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(g[i][j]<MAX) into[j]++;
}
}
/*零入度顶点入栈*/
int top=0; /*栈顶指针*/
for(int i=0;i<N;i++)
{
int j=0;
while(0!=into[j])
{
j++;
if(j>N)
{
cout<<"晕！有环"<<endl;
return false;
}
}
/*进入队列*/
ans[i]=j;
into[j]=-1;
/*计算Ve*/
for(int k=0;k<=i;k++)
{
if(g[ans[k]][j] < MAX)/*寻找前驱,k是ans中的标号*/
{
cout<<"ans["<<(char(k+'A'))<<"]= "<<ans[k]<<" ";
if(ve[j] < ve[ans[k]]+g[ans[k]][j])/*更新数据 ve[j]=Max(ve[k]+g[k][j])*/
{
ve[j] = ve[ans[k]]+g[ans[k]][j];
cout<<"ve["<<(char(j+'A'))<<"]= "<<ve[j]<<endl;
}
}
}
cout<<endl<<endl;
for(int k=0;k<N;k++)
{
if(MAX > g[j][k])
into[k]--;
}
}
for(int m=0;m<N;m++)
{
cout<<char(ans[m]+'A')<<" ";
}
cout<<endl;
for(int m=0;m<N;m++)
{
cout<<ve[m]<<" ";
}
cout<<endl;
/*计算vl, vl[i]=Min(v[k]-g[i][k])*/
/*初始化vl*/
int temp=ve[ans[N-1]];
for(int m=0;m<N;m++)
{
vl[m]=temp;
}
/*计算*/
for(int i=N-1;i>=0;i--)
{
for(int k=i;k<N;k++)
{
if(g[ans[i]][ans[k]] < MAX)/*是后继，k和i都是ans中的标号*/
{
if(vl[ans[i]] > vl[ans[k]]-g[ans[i]][ans[k]])/*更新数据*/
{
vl[ans[i]] = vl[ans[k]]-g[ans[i]][ans[k]];
}
}
}
}
for(int m=0;m<N;m++)
{
cout<<vl[m]<<" ";
}
cout<<endl;
/*找关键点，<i,j> ve[i]==vl[j]-g[i][j]*/
for(int i=0;i<N;++i)
{
for(int j=i;j<N;j++)
{
if(g[ans[i]][ans[j]] < MAX && ans[i]!=ans[j])/*存在一条边<i,j>*/
{
/*剩余时间为零，该边在关键路径上，其两个顶点为关键点*/
//cout<<vl[ans[i]]<<" "<<g[ans[i]][ans[j]]<<" "<<ve[ans[i]]<<endl;
if(vl[ans[j]]-g[ans[i]][ans[j]]==ve[ans[i]])
{
cout<<"<"<<char(ans[i]+'A')<<" , "<<char(ans[j]+'A')<<"> ";
}
}
}
}
cout<<endl;
return true;
}
int main()
{
/*输入数据*/
fstream fin("aaa.txt");
if(!fin)
{
cerr<<"Cannot open aaa.txt"<<endl;
}
/*初始化邻接表*/
for(int m=0;m<N;m++)
{
for(int n=0;n<N;n++)
{
if(m==n) g[m][n]=0;
else g[m][n]=MAX;
}
}
//memset(g, MAX, sizeof(g));
char i,j;
int k;
while(fin>>i>>j>>k)
{
g[(int)(i-'A')][(int)(j-'A')]=k;
}
for(int m=0;m<N;m++)
{
for(int n=0;n<N;n++)
cout<<g[m][n]<<" ";
cout<<endl;
}
/*拓扑排序*/
int noRing=topoSort();
if(!noRing)
{
return 0;
}
return 1;
}
E. 我想要一份能运行的实现关键路径算法，要C语言的，谢谢！
自己买本书看啦，数据结构的都有！
F. 求一条求“关键路径”的C程序
刚子,好样的,有结果了说一声!!!
G. 求关键路径的程序（最好是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,也许你已成为大神，就当一起学习吧
H. pmp如何计算关键路径
pmp计算关键路径的方法如下：
关键路径法（Critical Path Method）是一种用来预测总体项目历时的项目源网络分析技术。所谓“关键路径”，是指当我们完成了项目进计划后，在项目的网络图上，存在着若干条从项目启动到项目结束之间的路径，但是对其中一条（严格的来说，可能存在一条以上）路径上来说。
所谓正推法就是从项目的第一个活动到最后一个活动跟踪全部活动的先后关系，计知算出每个活动的最早开始时间（ES）和最早结束时间（EF）。
所谓倒道推法则是从最后一个活动开始向前追溯到第一个活动，计算出每个活动的最晚开始时间（LS）和最晚结束时间（LF）。
PMP作为项目管理资格认证考试，已在国际上树立了其权威性：
1、PMP为美国培养了一大批项目管理专业人才，项目管理职业已成为美国的“黄金职业”。在中国许多媒体已把PMP称为继MBA，MPA之后的三大金字招牌之一；
2、PMP认证已成为了一个国际性的认证标准，用英语、德语、法语、日语、韩语、西班牙语、葡萄牙语和中文等九种语言进行认证考试；
3、到目前为止，全球有80多万名PMP，中国大陆地区获得“PMP”头衔的已有18万多人，并逐年增长；
4、各国纷纷效仿美国的项目管理认证制度，推动了世界项目管理的发展。