資訊系統項目管理---之關鍵路徑

AOE網：在一個表示工程的帶權有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權值表示活動的持續時間，稱這樣的有向圖叫做邊表示活動的網，簡稱AOE網。AOE網中沒有入邊的頂點稱為始點（或源點），沒有出邊的頂點稱為終點（或彙點）。

AOE網的性質：

⑴ 隻有在某頂點所代表的事件發生後，從該頂點出發的各活動才能開始；

⑵ 隻有在進入某頂點的各活動都結束，該頂點所代表的事件才能發生。

關鍵路徑：在AOE網中，從始點到終點具有最大路徑長度（該路徑上的各個活動所持續的時間之和）的路徑稱為關鍵路徑。

關鍵活動：關鍵路徑上的活動稱為關鍵活動。關鍵活動：e[i]=l[i]的活動

　　由于AOE網中的某些活動能夠同時進行，故完成整個工程所必須花費的時間應該為始點到終點的最大路徑長度。關鍵路徑長度是整個工程所需的最短工期。

與關鍵活動有關的量：

⑴ 事件的最早發生時間ve[k]

　　ve[k]是指從始點開始到頂點vk的最大路徑長度。這個長度決定了所有從頂點vk發出的活動能夠開工的最早時間。

　　

　　

⑵ 事件的最遲發生時間vl[k]

　　vl[k]是指在不推遲整個工期的前提下,事件vk允許的最晚發生時間。

　　

　 

⑶ 活動的最早開始時間e[i]

　　若活動ai是由弧<vk , vj>表示，則活動ai的最早開始時間應等于事件vk的最早發生時間。是以，有：e[i]=ve[k]

⑷ 活動的最晚開始時間l[i]

　　活動ai的最晚開始時間是指，在不推遲整個工期的前提下， ai必須開始的最晚時間。若ai由弧<vk，vj>表示，則ai的最晚開始時間要保證事件vj的最遲發生時間不拖後。是以，有：l[i]=vl[j]-len<vk, vj>

示例：

　　

是以：

代碼實作：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

Status TopologicalOrder(ALGraph G, Stack &T)  { // 有向網G采用鄰接表存儲結構，求各頂點事件的最早發生時間ve(全局變量)。 // T為拓撲序列定點棧，S為零入度頂點棧。 // 若G無回路，則用棧T傳回G的一個拓撲序列，且函數值為OK，否則為ERROR。 Stack S; int count=0,k; char indegree[40]; ArcNode *p; InitStack(S); FindInDegree(G, indegree);  // 對各頂點求入度indegree[0..vernum-1] for ( int j=0; j<G.vexnum; ++j)     // 建零入度頂點棧S if (indegree[j]==0)  Push(S, j);  // 入度為0者進棧 InitStack(T); //建拓撲序列頂點棧T count = 0;   for ( int i=0; i<G.vexnum; i++)  ve[i] = 0;  // 初始化 while (!StackEmpty(S))  { Pop(S, j);  Push(T, j);  ++count;       // j号頂點入T棧并計數 for (p=G.vertices[j].firstarc;  p;  p=p->nextarc)  { k = p->adjvex;            // 對j号頂點的每個鄰接點的入度減1 if (--indegree[k] == 0) Push(S, k);   // 若入度減為0，則入棧 if (ve[j]+p->info > ve[k])  ve[k] = ve[j]+p->info; } //for  *(p->info)=dut(<j,k>) } if (count<G.vexnum)  return ERROR;  // 該有向網有回路 else return OK; }

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Status CriticalPath(ALGraph G)  { // G為有向網，輸出G的各項關鍵活動。 Stack T; int a,j,k,el,ee,dut; char tag; ArcNode *p; if (!TopologicalOrder(G, T))  return ERROR; for (a=0; a<G.vexnum; a++) vl[a] = ve[G.vexnum-1];    // 初始化頂點事件的最遲發生時間 while (!StackEmpty(T))       // 按拓撲逆序求各頂點的vl值 for (Pop(T, j), p=G.vertices[j].firstarc;  p;  p=p->nextarc)  { k=p->adjvex;  dut=p->info;     //dut<j,k> if (vl[k]-dut < vl[j])  vl[j] = vl[k]-dut; } for (j=0; j<G.vexnum; ++j)            // 求ee,el和關鍵活動 for (p=G.vertices[j].firstarc;  p;  p=p->nextarc)  { k=p->adjvex;dut=p->info;    ee = ve[j];  el = vl[k]-dut; tag = (ee==el) ? '*' : ' ' ; printf (j, k, dut, ee, el, tag);   // 輸出關鍵活動 } return OK; }