拓撲排序的另一個應用就是關鍵路徑的問題，關鍵路徑對應的是另一種網絡：AOE網絡。先回顧下拓撲排序中講到的AOV網絡，AOV網絡即“Activity On Vertex”，即圖上每一個頂點表示的是一個事件或者說一個活動，而頂點之間的有向邊則表示這兩個活動發生的先后順序。

在關鍵路徑這個問題中，AOE網絡指的是“Activity On Edge”，即圖上的每一條邊表示的是一個活動，頂點作為各個“入度邊事件”的匯集點，意思是，某個頂點，當所有的“入度邊事件”的活動全部完成后，才開始進行該頂點的“出度邊事件”。在AOE網絡中只有一個入度為零的點，稱作源頭頂點，和一個出度為零的目的頂點。AOE網絡通常用來安排一些項目的工序。

上圖表示的就是AOE網絡中的，有向邊上方表示該活動的持續時間，也就是完成該活動要多長時間，有向邊下方表示該活動的機動時間，機動時間是什么呢，下面等拿例子來講解時再解釋。頂點里又分為三部分，一部分是存放頂點的編號，另外兩部分分別存放活動的最早完成時間（即到達該點用時最短），和最晚完成時間（即到達該點用時最長）。

下面根據一個具體的例子來看到底什么是AOE網絡和關鍵路徑：

在下面的有向無環圖中，V1是源頭頂點（即開始點），到V10結束，每一條邊代表一個活動，有向邊的方向表示活動完成后到達哪一個匯集點。有向邊上方表示的是活動完成所需要的時間（也是持續時間）。假設活動a7和a8想要開始，那么必須等到活動a4和a5都完成后，a7和a8才能開始。

還有一種更復雜的情況是：如果活動a7和a8要開始，必須要等活動a4、a5和a6都完成后，才能開始a7和a8活動（因為在AOE網絡中有些活動是可以并行地進行的）。這樣的情況怎么辦？我們不可以把V5和V6頂點連接起來，為什么？因為我們看a9這個活動，它的開始與否和活動a4，a5均無關系，活動a9只需等待活動a6完成他就可以開始了，所以如果我們把V5和V6頂點連接起來，是不行的。那要怎么辦？方法是用一個無向虛線（標記線）把V5和V6連接，邊上的權值設為0，如圖：

接著根據這個有向無環圖，我們看看從開始到結束整個工程活動需要的最短時間是多少？答案是從開始點出發到完成點的最長路徑的長度（這里的最長路徑長度指的是路徑上各個活動持續時間之和，不是指路徑上邊的數目）。從開始點到結束點的最長路徑就叫做關鍵路徑。從開始結點V1開始，它的最早完成時間自然是0了，然后到V2結點，V2結點的最早完成時間是5，同理V3結點最早需要4天完成，V4結點最早需要6天完成。

接著到下一組，從V4到V6頂點，活動a6需要7天，所以V6上填上6+7=13，也就是說到達V6需要最早完成時間是13天。對于V5這個頂點，它的完成時間有三個，分別是5+3=8，4+2=6和13+0=13。這里我們就要選一個最大的填進去，因為V5的“出度邊事件”要進行，也就是活動a7和a8要開始的話，必須等齊a4，a5和a6三個活動結束后才能開始，所以在a4、a5和a6中選一個完成時間最大的，就能確保三個活動都能完成。

到這里我們就知道程序大概要怎么寫了：

首先我們需要一個Earliest[ ]數組來存放每一個頂點的最早完成時間，Earliest[ 1 ]=0代表的就是開始結點V1的最早完成時間是0，對于圖中每一個頂點對<i, j>，Earliest[ j ]的值也就是j結點的最早完成時間就等于Earliest[ i ]+C<i, j>（也就是前一個結點i的最早完成時間加上i和j之間的有向邊的權值），當結點j的入度邊不止一條的時候，Earliest[ j ]存放的就是所有入度邊中最大的值。

按照這個思路，我們可以把圖里接下來的頂點的完成時間都填好：

到最后V10結束結點等于29，也就是說整個圖的所有活動的最短完成時間是29天。

最后到來看看這個圖中活動的機動時間，什么是機動時間呢，就是指圖中這些活動中，有哪些活動是一直進行下去的，沒有休息時間的。例如活動a10需要3天完成，而獲得a11需要2天，則a11有1天的休息時間等待a10完成，a11的這一天休息時間就是所謂的“機動時間”。

我們用e（i）來表示活動ai的最早完成時間，l（i）表示ai的最遲開始時間，機動時間要怎么算呢？看圖來說，我們從結束結點開始倒推，在保證整個工期都不推遲的情況下，也就是第29天開始，反推回去，看結點V9，活動a12需要5天，就是說在保證整個工期能在29天完成的情況下，V9的最晚開始時間（也就是最遲完成時間）是29-5=24，就是說活動a12最遲必須在第24天就要開始工作了。V7結點和V8結點同理，V7結點最遲必須在第24-3=21天就開始工作，V8結點最遲必須在第24-2=22天開始就工作。

接著看V5結點，從V8倒推到V5，就是22-7=15，a8活動最遲第15天就要開始工作。而從V7倒推到V5的話，21-8=13，a8活動最遲第13天就要開始工作，這里出現兩個不同的值，怎么選？答案是選最小值13，因為如果選擇第15天開工，那么對于活動a7來說，就延遲了兩天開工了，這樣就不能保證后面能在29天內完成整個工程，所以遇到兩種不同的最晚開始時間時，我們要選最小的，這樣才能保證整個工期不被延誤。

同樣的，看V6結點，從V8結點倒推到V6結點，22-5=17天，也就是活動a9的最遲開始時間可以是在第17天時才開工？答案是不行的，因為V6結點和V5結點有個虛線連著呢，V6結點，也就是活動a9的最遲開始時間同樣是13天。

從這里就可以看出我們的求機動時間的倒推時的推斷是，需要一個Latest[ ]數組存放每一個結點的最遲開始時間，一開始初始化結束結點的Latest[ 10 ]=Earliest[ 1 ]，也就是29。然后倒推時，Latest[ i ]就等于Last[ j ]-C<i, j>.。如果某個結點有多個出度邊，那么就選擇最小值賦給Last[ i ]就可以了。

按照這個推斷，就可以把剩下的頂點的最晚開始時間都算出來：

V1頂點有三種選擇，V2到V1等于5，V3到V1等于7，V4到V1等于0，因為我們要選擇最小值，所以V1填上0。

最后來看看每個結點的機動時間，我們從頭開始看，活動a1需要工作5天才完成，到達V2結點中，最遲開始時間是10，也就是說活動a4最遲在第10天開始工作都不會耽誤整個工期，而a1從第0天開始只需工作5天就能完成，所以活動a1的機動時間就是10-0-5=5，五天。活動a2最遲在第11天開始工作就可以了，而活動a2只需要4天就可以完成，所以a2的機動時間是11-0-4=7，七天。活動a3等于6-0-6=0，所以活動a3機動時間等于0，也就是說活動a3完成后就要開始下一個活動了，中間沒有“休息時間”。

同理可看出，a4的機動時間是13-5-3=5。a5的機動時間是13-4-2=9。a6是13-6-7=0。這樣我們就可以把所有的機動時間都算出來：

我們假設用e(i)表示活動ai的最早開始時間，用l(i)表示活動的最遲開始時間，那么兩者之差l(i)-e(i)表示活動ai的機動時間，把e(i)=l(i)的活動我們稱為“關鍵活動”。關鍵路徑上所有的活動都是關鍵活動。回到關鍵路徑的問題，關鍵路徑有可能不止一條。所以找出關鍵路徑即找出路徑上所有活動都是關鍵活動的路徑即可。

/*拓撲排序*/ bool TopSort(ListGraphNode MyGraph, Vertex TopOrder[]) {/*TopOrder[]數組用來順序存儲排序后的頂點的下標*//*在拓撲排序完成后直接順序輸出TopOrder[]里的元*//*素就能得到拓撲排序序列*/ int i;int Indegree[MaxVertex], cnt;/*Indegree數組是圖中頂點的入度,cnt是計數器*/Vertex V;/*掃描V頂點的鄰接點*/PtrlPointNode W; /*鄰接表方式表示圖*/Queue PtrQ=Start();for (i=0; i<MaxVertex; i++) {PtrQ->Data[i]=-1;}/*初始化入度數組*/for (V=0; V<MyGraph->numv; V++) {Indegree[V]=0;}/*遍歷圖,得到圖中入各頂點的入度情況并存入Indegree數組中*/for (V=0; V<MyGraph->numv; V++) {for (W=MyGraph->PL[V].HeadEdge; W; W=W->Next) {Indegree[W->Tail]++;}}/*將所有入度為0的頂點入列*/for (V=0; V<MyGraph->numv; V++) {if (Indegree[V]==0) {Push(PtrQ, V);}}/*開始拓撲排序*/cnt=0; /*初始化計數器為0*/while (PtrQ->End!=PtrQ->Head) {V=Delete(PtrQ);/*出列一個入度為0的頂點*/TopOrder[cnt++]=V;/*拓撲排序數組里記錄該出列頂點的下標*//*遍歷對于V的每個鄰接點W->PL.HeadEdge.index*/ for (W=MyGraph->PL[V].HeadEdge; W; W=W->Next) {/*若刪除V能使該頂點的入度為0*/if (--Indegree[W->Tail]==0) {/*把該頂點入列*/Push(PtrQ, W->Tail);}/*同時更新Earliest數組的值*/if ((Earliest[V]+W->Weight)>Earliest[W->Head]) {Earliest[W->Tail]=Earliest[V]+W->Weight;} }}/*最后判斷*/if (cnt!=MyGraph->numv) {return false;/*說明該圖里有回路,返回false*/} else {return true;} }

在拓撲排序過程中，我們就同時更新Earliest數組，把每一個頂點的最早完成時間填入到數組中。

/*關鍵路徑*/ bool CriticalPath(ListGraphNode MyGraph, int TopOrder[]) {int k, ee, el;PtrlPointNode W;Queue List=Start();/*得到后面逆序用*/for (k=0; k<MyGraph->numv ; k++) {Push(List, TopOrder[k]); } /*初始化Lastest數組*/ for (k=0; k<MyGraph->numv; k++) {Lastest[k]=Earliest[MyGraph->numv-1];}/*開始關鍵路徑*/while (List->End!=List->Head) {k=Delete(List);/*出列一個入度為0的頂點*//*遍歷對于V的每個鄰接點W->PL.HeadEdge.index*/ for (W=MyGraph->PL[k].HeadEdge; W; W=W->Next) {if (Lastest[k]>(Lastest[W->Tail]-W->Weight)) {Lastest[k]=Lastest[W->Tail]-W->Weight;} }//printf("關鍵路徑為:"); for (k=0; k<MyGraph->numv; k++) {W=MyGraph->PL[k].HeadEdge;while (W) {ee=Earliest[k];el=Lastest[W->Tail]-W->Weight;if (ee==el) {/*兩值相等說明它們是關鍵活動*/printf("v%d--v%d=%d", MyGraph->PL[k].HeadEdge->Tail, MyGraph->PL[W->Head].HeadEdge->Tail, W->Weight);}W=W->Next;} }} }

在關鍵路徑的計算過程中再逆序計算出最遲開始時間即可。

完整代碼在個人代碼云：

https://gitee.com/justinzeng/codes/9jbqdrhgn8xl31y6vsw2u75

總結

以上是生活随笔為你收集整理的AOE网络-关键路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。