關鍵路徑演算法

『壹』 怎麼實現關鍵路徑演算法動態演示

短路徑算簡單由起點層層向外尋找終點種算效率低幾十節點圖沒問題

另外種思路比較適合少量節點圖由計算機預先計算每節點至其節點短路徑存儲資料庫短路徑數據表至於兩條線路走三條線路走問題解決

『貳』 關鍵路徑法的公式計算

上面介紹了活動的最早和最遲時間的計算方法，以上的過程可以用比較簡單的公式來表達。 上面所講述的方法，我們一般稱為節點計演算法，節點和活動的最早時間按照正推法進行計算，起點節點未規定時間時，我們取其時間為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,也許你已成為大神，就當一起學習吧

『拾』 關鍵路徑演算法的時間復雜度

所謂關鍵路徑，就是從工程開始到工程結束所用時間最長的路徑。這是因為，在途中的每一個階段開始之前，都要保證此前的准備工作都已完成，要不然後續工程會無法完成，在尋找路徑時，只能一條路徑一條路徑的比較。本題結果是