【正文】 e(i)=l(i)的活動。通常， AOE網(wǎng)可用來估算工程的完成時間。還可以定義一個活動的最遲開始時間 l(i)，這是在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的時間。 ?先將拓撲排序算法 ，則算法。i。 ? int indegree[MAXVEX]。i++) printf(V%1d ,topo[i]+1)。 ? for(i=0。 ? for(i=0。k=0。 ? i++。實際上，求關(guān)鍵路徑的方法本身最初就是與維修和建造工程一起發(fā)展的。 ? } ?void main() /*主程序 */ ?{ ALGraph G。 ? while(p!=NULL) ? { k=padjvex。 ? for(i=0。 ? insert(G,6,8,2)。 /*找表尾 */ ? pnextarc=temp。 ? return FALSE。 ? top=k。 /* 圖的頂點個數(shù) */ ? }ALGraph。 ?由此得到求關(guān)鍵路徑的算法： ? (1)輸入 e條弧 j， k，建立 AOE網(wǎng)的存儲結(jié)構(gòu)； ? (2)從源點 v0出發(fā)，令 ve[0]=0，按拓撲有序求其余各頂點的最早發(fā)生時間 ve[i] (1≤i≤n1)。路徑長度最長的路徑叫做關(guān)鍵路徑 (Critical Path)。與每個活動相聯(lián)系的數(shù)是執(zhí)行該活動所需的時間。 ? 這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提下進行。 /* 邊表頭指針 */ ? }VNode,AdjList[MAXVEX]。 ? while(p) /* 刪除以該頂點為起點的邊 */ ? { k=padjvex。 /*ptopo數(shù)組存放拓撲序列 */ ? p=[j].firstarc。 ? p=[a].firstarc。 ? insert(G,4,6,9)。 ? p=pnextarc。 ? for(j=0。 /*計算數(shù)組 vl， vl存放事件可能的最遲發(fā)生時間 */ ? counte_l(G,ve,vl,ee,el)。只有在不改變網(wǎng)的關(guān)鍵路徑的情況下，提高關(guān)鍵活動的速度才有效。 ? p=pnextarc。 ? while(p!=NULL) ? { j=padjvex。 /*ee數(shù)組賦初值 */ ? for(k=0。 ? insert(G,0,1,6)。 ? } ? void insert(ALGraph amp。i。i。 ? typedef struct ArcNode ? { int adjvex。顯然，關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，因此提前完成非關(guān)鍵活動并不能加快工程的進度。關(guān)鍵路徑 ?與 AOV網(wǎng)相對應(yīng)的是 AOE網(wǎng) (Activity On Edge)即邊表示活動的網(wǎng)。我們把 l(i)=e(i)的活動叫做關(guān)鍵活動。 /*存放頂點信息的字符串 */ ? typedef float AdjType。 /*頂點入度數(shù)組賦初值 */ ? for(i=0。 /* 求出圖中所有頂點的入度 */ ? for(i=0。 ? return TRUE。i++) //給頂點指針域賦初值 ? [i].firstarc=NULL。i++) ve[i]=0。 ? p=[i].firstarc?；〉男蛱栕缘谝粋€頂點開始到最后一個頂點止順序編號。由此可見，關(guān)鍵活動的速度提高是有限度的。 /*計算數(shù)組 ee,el并輸出結(jié)