關鍵路徑

關鍵路徑通常（但並非總是）是決定項目工期的進度活動序列。它是項目中最長的路徑，即使很小浮動也可能直接影響整個項目的最早完成時間。關鍵路徑的工期決定了整個項目的工期，任何關鍵路徑上的終端元素的延遲在浮動時間為零或負數時將直接影響項目的預期完成時間（例如在關鍵路徑上沒有浮動時間）。 ^[2]  但特殊情況下，如果總浮動時間大於零，則有可能不會影響項目整體進度。

一個項目可以有多個、並行的關鍵路徑。另一個總工期比關鍵路徑的總工期略少的一條並行路徑被稱為次關鍵路徑。最初，關鍵路徑方法只考慮終端元素之間的邏輯依賴關係。關鍵鏈方法中增加了資源約束。關鍵路徑方法是由杜邦公司發明的。

A、從開始頂點 v₁ 出發，令 v_e(1)=0，按拓撲有序序列求其餘各頂點的可能最早發生時間。 ^[3] 

V_e(k)=max{v_e(j)+dut(<j,k>)} , j ∈ T 。其中T是以頂點v_k為尾的所有弧的頭頂點的集合（2 ≤ k ≤ n）。

如果得到的拓樸有序序列中頂點的個數小於網中頂點個數n，則説明網中有環，不能求出關鍵路徑，算法結束。

B、從完成頂點

出發，令

，按逆拓撲有序求其餘各頂點的允許的最晚發生時間：

v_l(j)=min{v_l(k)-dut(<j,k>)} ,k ∈ S 。其中 S 是以頂點v_j是頭的所有弧的尾頂點集合（1 ≤ j ≤ n-1）。

C、求每一項活動ai（1 ≤ i ≤ m）的最早開始時間e(i)=v_e(j)，最晚開始時間l(i)=v_l(k)-dut(<j,k>) 。

若某條弧滿足 e(i)=l(i) ，則它是關鍵活動。

（1）AOE網

用頂點表示事件，弧表示活動，弧上的權值表示活動持續的時間的有向圖叫AOE（Activity On Edge Network）網。在建築學中也稱為關鍵路線。AOE網常用於估算工程完成時間。例如：圖1 是一個網。其中有9個事件v₁,v₂,…,v₉；11項活動a₁,a₂,…,a₁₁。每個事件表示在它之前的活動已經完成，在它之後的活動可以開始。如 v₁表示整個工程開始，v₉ 表示整個工程結束。V₅表示活動a₂和a₃已經完成，活動a₇和a₈可以開始。與每個活動相聯繫的權表示完成該活動所需的時間。如活動a₁需要6個時間單位可以完成。

一個AOE網的關鍵路徑可以不止一條。

只有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。只有在進入某一頂點的各有向邊所代表的活動都已經結束，該頂點所代表的事件才能發生。表示實際工程計劃的AOE網應該是無環的，並且存在唯一的入度為0的開始頂點和唯一的出度為0的完成頂點。

（2） 活動開始的最早時間e(i)；

（3） 活動開始的最晚時間l(i) 定義e(i)=l(i）的活動叫關鍵活動；

（4） 事件開始的最早時間v_e(i)；

（5） 事件開始的最晚時間v_l(i)。

（1） 完成整個工程至少需要多少時間；

（2） 哪些活動是影響工程的關鍵。

1956年，美國杜邦公司提出關鍵路徑法，並於1957年首先用於1000萬美元化工廠建設，工期比原計劃縮短了4個月。杜邦公司在採用關鍵路徑法的一年中，節省了100萬美元。

（1） 輸入e條弧<j,k>，建立AOE網的存儲結構；

（2） 從源點v₁出發，令v_e(1)=0，求 v_e(j) ,2<=j<=n；

（3） 從匯點v_n出發，令v_l(n)=v_e(n)，求 v_l(i), 1<=i<=n-1；

（4） 根據各頂點的v_e和v_l值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關鍵活動。

求關鍵路徑是在拓撲排序的前提下進行的，不能進行拓撲排序，自然也不能求關鍵路徑。

（1） 求關鍵路徑必須在拓撲排序的前提下進行，有環圖不能求關鍵路徑；

（2） 只有縮短關鍵活動的工期才有可能縮短工期；

（3） 若一個關鍵活動不在所有的關鍵路徑上，減少它並不能減少工期；

（4） 只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。

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[G.vexnum-1];

while(!StackEmpty(T))

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p->adjvex; dut=*(p->info);

if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;

}

for(j=0;j<G.vexnum;++j)

for(p=G.vertices[j].firstarc;p;p=p->nextarc)

{k=p>adjvex; dut=*(p->info);

ee=ve[j]; el=vl[k];

tag=(ee==el)?’*’：’’；

printf(j,kdut,ee,el,tag);

}

} ^[4] 

#include <iostream>

#include <cstdio>

#include<string.h>

using namespace std;

int n,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];

void init()

{

int i,a,b,c;

scanf("%d%d",&n,&m);

for (i=1;i<=m;i++)

{

scanf("%d%d%d",&a,&b,&c);

w[a][b]=c;

prev[b]++;

}

}

inline void Newq(int v)

{

r++;

queue[r]=v;

}

inline void Del(int v)

{

int i;

for (i=1;i<=n;i++)

if (w[v][i])

{

prev[i]--;

if (!prev[i])

Newq(i);

}

}

void topo()

{

for (int i=1;i<=n;i++)

if (!prev[i])

Newq(i);

while (r<n)

{

l++;

Del(queue[l]);

}

}

void crucialpath()

{

int i,j;

memset(Time,0,sizeof(Time));

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if ((w[j][queue[i]]) && (Time[j]+w[j][queue[i]]>Time[queue[i]]))

{

Time[queue[i]]=Time[j]+w[j][queue[i]];

Pos[queue[i]]=j;

}

}

void print()

{

printf("%d\n",Time[n]);

int i=n,k=0;

while (i!=1)

{

k++;

path[k]=i;

}

for (i=k;i>1;i--)

printf("%d ",path[i]);

printf("%d\n",path[1]);

}

int main()

{

init();

topo();

crucialpath();

print();

return 0;

}