上篇部落格我們介紹了AOV網的拓撲序列，請參考《資料結構(七) AOV網的拓撲排序(Swift面向對象版)》。拓撲序列中包括項目的每個結點，沿着拓撲序列将項目進行下去是肯定可以将項目完成的，但是工期不是最優的。因為拓撲序列是一個串行序列，如果按照該序列執行項目，那麼就是串行執行的。我們知道在一個項目中的一些子工程是可以并行來完成的，這也就類似我們的多線程。今天我們要解決的問題就是找出一個關鍵路徑，是工期最優并保證工程的完成。什麼是關鍵路徑，我們在下方會進行詳細介紹。
一、關鍵路徑概述
在聊關鍵路徑之前，我們先看一個簡單的執行個體，如下圖所示。我們将下方這個有向無環圖看做是整個工程，将每個節點看做是該項目工程的一個子工程。子工程間又有一定的優先級。在下方圖中，A的優先級最高。A做完後，B、C才可以進行開發。B、C完成後，我們才可以開發D。從下圖中我們不難看出，該圖的拓撲序列為A, B, C, D。如果我們按照串行的方式來完成此工程的話，那麼工程完成的順序可以是A-5->B, A-8->C, B-3->D, C-10->D。總時間為26。
從上面這個序列中我們顯然可以看出來這不是最優的，因為A->B, A->C可以同時進行，B->D和C->D也可以同時進行。在允許某些子工程同時進行的情況下，A->B和A-C可以同時進行，因為A->B所需時間小于A->C所需時間，是以我們選擇A->C。在A->C執行這8個小時的時間裡，A->B和B->D已經執行完了，就剩下C->D了，是以關鍵工期為A->C->D=18。
在求關鍵路徑的算法中，我們先求出每個事件的最早完成時間。在事件最早完成的時間集合中，工程最後一步完成的時間就是我們工程完成的最優時間。然後在工程時間最優的情況下求出每個事件最晚完成時間。如果某個時間最早的完成時間與最晚的完成時間相同，那麼該事件就是我們的關鍵事件，該事件就位于我們關鍵路徑中。如果這樣叙述有些抽象，那麼我們就拿下方這個簡單圖來做個類比。
在上方這個有向無環圖中，我們可以求出每個事件最早發生的時間。下方截圖就是每個事件所對應的最早完成的事件，因為D是工程的尾結點，是以該工程完成的最早時間也就是D完成的最早時間，即工程完成的最早時間為18。
在整個工程最早完成的時間下，我們可以從後往前推出每個子工程最晚的完成時間。這最晚完成時間就是在不耽誤整個工程最小工期的前提下，最晚的完成時間。每個工程的最晚完成時間我們可以倒着推出。也就是從D=18往後推出。下方就是每個工程在保證整個工期是的完成時間是18的前提下的最晚完成時間。
對比上了最早完成時間和最晚完成時間，我們可以看出A, C, D這三個結點的最早完成時間與最晚完成時間相同，是以是我們的關鍵結點。這幾個結點連接配接的路徑就是我們的關鍵路徑。是以上圖中的關鍵路徑就是A->C->D。
二、關鍵路徑算法的具體步驟
第一部分因為示例比較簡單，算是我們本篇部落格的開胃小菜，接下來進入我們本篇部落格真正的主題。在本部分，我們還是以原理圖為主，本部分不會給出具體的代碼實作，我們隻講原理。本篇部落格是在上篇部落格的基礎上實作的，因為每個路徑的最早執行的時間的計算依賴于拓撲序列，是以我們依然會采用上篇部落格我們拓撲序列所使用的圖的結構。下方就是我們要求關鍵路徑的有向無環圖。如果你看過前幾天部落格的話，那麼對下方這個圖的結構應該是非常熟悉了吧，今天我們依然會使用下方這個圖來做我們的執行個體。
1.最早完成時間計算
首先我們根據拓撲排序的過程來計算出每個結點最早完成時間。最早完成時間計算的計算過程就是在拓撲排序的過程中添加一段記錄每個結點完成的最早時間，下方就是求最早完成時間的整個執行個體圖，下方會給出每一步的詳細介紹。下方是由拓撲排序計算最早完成時間的具體步驟，并且給出了每一步的計算規則。
其實下方這個步驟與上一篇部落格中拓撲排序的步驟大同小異，隻是在其基礎上引入了一個數組。數組中記錄的就是索引對應結點的最早完成時間，具體步驟如下所示。下方的每一步其實就是拓撲排序的步驟，隻是加入了每個結點最早完成時間的計算，因為上篇部落格對拓撲排序做了詳細的叙述，在此就不做過多贅述了。
-
（1）、首先我們先建立好一個數組用于存儲每個結點最早完成的時間，數組元素的初始值為零，因為其實結點的完成時間就是0。
-
（2）、這一步中，結點A加入了拓撲序列，是以我們可以計算出與A結點相連結點的完成時間。因為A-10->B, A的完成時間為0，0+10，是以B的此刻的完成時間為10，同理我們可以求出F的此刻完成時間是11。
-
（3）、在第三步中，F進入拓撲序列，與F結點相連的結點是G和E。是以我們可以由F的此刻的完成時間11和F->G所需完成的時間17，求出G的此刻的完成時間11+17=28。同理我們可以求出結點E的此刻的完成時間為11+26 = 37。
-
（4）、本步驟中E結點進入拓撲序列。由上面一步我們知道E的完成時間是37，那麼不難得出與E相連的結點D目前的完成時間是37+20 = 57。同理，H結點目前的完成時間為37+7=44。
-
（5）、該步驟中B結點進入拓撲序列，與B相連的結點有B-16->G, B-12->I, B-18->C。我們先來從B到G這條路徑中G的完成時間，由B->G的完成時間為10+16=26。我們之前求的F->G這條路徑中G的完成時間是28，因為B和F都是G的前提，B和F有一個完不成，G就無法提前完成，是以我們選擇F->G這條路徑來作為G的完成時間，因為FG(28)>BG(26), 低于28這個時間，G就完不成，是以此輪不更新G的完成時間。同理，此輪我們求出I的完成時間為10+12=22，C的完成時間為10+18=28。
-
（6）、本步驟中C進入拓撲序列，由C-8->I可求出C路徑中I的完成時間是28+8=36，與之前求得B->I路徑中I的完成時間22相比要大，是以更新I的完成時間為36。由C-22->D可求出該路徑中D的完成時間為28+22=50，而上面我們計算的D的完成時間為57，50<57, 此輪不更新D的完成時間。
-
（7）、I進入拓撲序列，由I-21->D，可知，D在該路徑中的完成時間為36+21=57。與之前D的完成時間相等，此輪也不更新D的完成時間。
-
（8）、G進入拓撲序列。有G-19->H可以求出，G路徑上的H的完成時間為28+19=47。我們之前計算的H的完成時間為44，是以本輪将H的完成時間更新為47。
-
（9）、H進入拓撲序列。有H-16->D可以求出本輪D的完成時間為47+16=63。63大于上面計算的D的完成時間57，是以将D的完成時間更新為63。
-
（10）、D進入拓撲序列，因為D為終點，是以拓撲排序結束，我們最早完成時間也計算完畢。
經過上面這些步驟，上面數組中所存儲的就是每個結點的最早完成時間，如下所示：
2.計算最遲完成時間
上面由拓撲排序從前往後計算的完成時間就是我們每個結點的最早完成時間，接下來我們将要計算每個結點在總時間不變的情況下，最晚完成時間。每個結點的最晚完成時間我們要從後往前計算，因為整工程的總時間确定，從後往前我們就可以計算每個結點最晚完成時間。下方就是計算最晚完成時間的所有的詳細步驟。
因為我們是按照拓撲排序的序列從後往前計算的最晚完成時間，是以我們将拓撲序列從頭到尾依次進入棧。然後以出棧的順序來計算最晚完成時間，此刻的出棧順序就是拓撲排序的逆序。是以下方計算每個結點的最晚完成時間時要借助棧的資料結構來完成。和上述計算最早完成時間類似，依然是将完成時間存入數組中，然後根據我們計算的資料進行更新完成時間。
下方是對最晚完成時間示例圖的詳細介紹：
-
（1）：首先初始化我們存儲最晚完成時間的數組，因為整個工程的完成時間時63，是以我們初始化每個結點的最晚完成時間就以63為準。因為再晚也不會超過63。在該步驟中，我們将D出棧。因為D是最後一個完成的結點，是以其最晚完成時間就是63，我們不做任何的更新。
-
（2）：接着我們将H出棧，有H-16->D可知，H此刻的完成時間為63-16= 47，更新H對應的完成時間。
-
（3）：将G出棧，由G-19->H可以計算出GH這條路徑中G的完成時間為47-19=28，由G-24->D這條路徑可以計算出GD這條路徑中G的完成時間為63-24=39。因為28<39, 為不耽誤H的正常進行，是以G此刻的最晚完成時間為28。
-
（4）：将I出棧，由I-21->D這條路徑，我們可以計算出，此刻I的最晚完成時間為63-21=42。
-
（5）：将C出棧，由C-8->I可以計算出C在CI這條路徑中最晚完成時間為42-8=34，由C-22->D這條路徑可以計算出CD這條路徑中C的最晚完成時間為63-22=41。因為34<41, 為了不耽誤I的完成，是以C的最晚完成時間為34。
-
（6）：将B出棧：有B-16->G可以計算出,BG這條路徑的最晚完成時間為28-16=12，同理可計算出BI這條路徑中B的最晚完成時間為42-12=30，BC這條路徑中B的最晚完成時間為34-18=12。是以B的最晚完成時間為12。
-
（7）：将E出棧，由E-20->D中可以求出ED這條路徑中E的最晚完成時間為63-20=43，同理可求出EH這條路徑中E的最晚完成時間為47-7=40，最有E的最晚完成時間為40.
-
（8）：将F出棧，由F-26->E可求出FE這條路徑中F的最晚完成時間為40-26=14，有F-17->G這條路徑中可以求出FG這條路徑中F的最晚完成時間為28-17=11，是以F的最晚完成時間為11。
-
（9）：将A出棧，由A-10->B可以求出，AB這條路徑中A的最晚完成時間為12-10=2，同理AF這條路徑中A的最晚完成時間為11-11=0，是以A的最晚完成時間為0。至此棧中的元素為空，我們的最晚完成時間就計算完畢了，示例圖如下所示。
經過上述步驟我們就可以計算出每個結點的最晚完成時間，如下所示：
3.計算關鍵路徑
由每個結點的最早完成時間和最晚完成時間我們就可以計算出我們的關鍵路徑了。因為工程的總時間是固定的，那些最早完成時間等于最晚完成時間的結點就是我們所要找的關鍵結點。下方就是在圖周遊時，根據最早完成時間和最晚完成時間的對比，求出關鍵路徑具體步驟。
-
（1）：從最早和最晚完成時間中我們可以看出來關鍵結點有A, D, F, G, H。我們可以在周遊圖時給出這幾個結點的先後順序。
-
（2）：從A結點開始周遊，A與F,B相連，F的最晚時間可最早完成時間相等,是以發展成關鍵路徑,A-11->F。
-
（3）：F與E和G相連，G的最晚和最早完成時間等，是以此刻的關鍵路徑為A-11->F-17->G。
-
（4）：G與D和H相連，G的最晚時間是47-19=28得到的，是以此刻的關鍵路徑為A-11->F-17->G-17->H。
-
（5）：以此類推，可以計算出關鍵路徑為A-11->F-17->G-17->H-16->D。
三、關鍵路徑的代碼實作
上面給出了關鍵路徑的詳細求解步驟，如果你将上面每個步驟搞明白後，給出代碼實作并不難。接下來我們就會根據上面的步驟給出具體的代碼實作。當然我們依然使用Swift語言實作，當然使用的是目前Swift最新版本，也就Swift3.0。
從上面的步驟中我們可以大體分為三步：
-
第一步：根據拓撲序列求出每個結點最早完成時間。
-
第二步：根據拓撲的逆序列，結合着最早完成時間求出每個結點的最晚完成時間。
-
第三步：結合着最早完成時間和最晚完成時間，根據圖的結構求出關鍵路徑。
接下來我們的代碼實作也是根據上面這三步來實作的。進入我們代碼實作的部分。
1.計算最早完成時間
本部分代碼與上篇部落格中拓撲排序的代碼差不多，就多了下方紅框中的部分。下方多出的代碼就是在拓撲排序的過程中求出每個結點的最早完成時間，然後存儲在earliestTimeOfVertex數組中。因為代碼與拓撲排序的代碼類似，是以在此就不做過多贅述了。
2.計算最晚完成時間
計算為最早完成時間後，我們工程的整個工期也就是定了。根據這個固定的工期，然後結合着拓撲排序的倒序，就可求出每個結點最晚完成的時間。下方這段代碼就是計算每個結點的最晚完成時間。就是從後往前計算。
首先将拓撲序列入棧，也就是将拓撲序列逆序的一個過程。然後不斷從棧中取值，取一個結點就要計算該結點的最晚完成時間。與該結點相連結點的最晚時間 - 權值= 該結點的最晚完成時間。在這個過程中取最小的哪個時間，就是目前結點最晚完成的時間。具體代碼如下所示：
上面兩步計算完最早完成時間和最晚完成時間後，接下來我們就要開始計算我們的關鍵路徑了。下方代碼其實就是在圖的層次周遊時，查找那些最早完成時間與最晚完成時間相等的結點，如果相等，則是關鍵路徑上的結點，然後将該節點進行輸出。
當然下方代碼中if後方的等式是個關鍵，将該等式翻譯成文字就是：結點最早完成時間 == 下一個結點的最晚完成時間 - 該節點到下一個結點的權值 == 該結點最晚完成時間，如果上面這個等式成立，那麼就說明該結點是關鍵結點，我們将其進行輸出。具體代碼如下所示。
4.測試用例
上面三步是關鍵路徑計算的所有代碼，接下來又到了我們測試的時刻了。下方就是我們的測試用例，首先我們根據圖的結點和關系建立有向圖。然後輸出我們建立的這個有向無環圖。為了清晰的能看出每一步的執行，我們并沒有将三步封裝成一個函數來調用。下方的第一步就是求最早完成時間，第二步就是計算最晚完成時間，第三步就是計算我們的關鍵路徑了。
下方就是我們的測試用例的輸出結果了，輸出結果還是比較直覺的，有圖有真相，在此就不做過多贅述了。
好今天的部落格就到這兒，下幾篇部落格依然是關于資料結構的，敬請期待。今天部落格中的Demo依然會在github上進行分享。下方是分享位址。
github分享位址：https://github.com/lizelu/DataStruct-Swift/tree/master/CriticalPath
作者：青玉伏案
出處：http://www.cnblogs.com/ludashi/
本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。
收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]