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、各國紛紛效仿美國的項目管理認證制度，推動了世界項目管理的發展。