關鍵路徑演算法

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，同上