浙江大學-數據結構-拓撲序列-8.2.2

最後作為對拓撲排序的重要應用，我們來介紹一下關鍵路徑的問題，關鍵路徑的問題對應的是另外一類網路，我們前面講了一個AOV，就是Activity On Vertex,每一個頂點表示的是一個事件或者一個活動，另外一類網路叫AOE(Activity On Edge),在這樣的網路裡頭，每一條邊代表的是一套工序或者說是一個活動，這種網路一般是用於安排很龐大的項目，那這個龐大的項目會分成很多道工序，工序和工序之間呢，是有先後的依賴關係的，AOE的網路就經常用於解決這類問題，那麼在AOE網路裡頭，我們的活動是表示在邊上，頂點呢，表示的是這個活動到達這個頂點的時候就結束了，

通常在畫這個網路的時候，我們把一個頂點分成3塊，在邊的上面寫的是這個活動的持續時間，就是這個小組要完成這道工序它一共需要多少天的時間，這個數字寫到邊的上面，邊的下面寫的是機動時間，什麼是機動時間回頭我們再說，每一個頂點我們把它分成3塊，這個區域我們一般寫頂點編號，

比如說如果是 的話，我們寫一個j在這裡(頂點編號),上面這塊區域我們記得是這個頂點所有的任務最早的完成時間，叫Earliest,

下面這個區域相應的記得是所有的這些項目最晚需要完成的時間，我們叫做Lastest,

到底什麼意思呢？還是來看一個具體的例子，

比如說這是一個整個大的project,我們從這個頂點表示開始，到達最右邊頂點的時候表示整個項目結束，每一條邊代表一件事情，每件事情按照這個順序，相互依賴的順序完成了以後，到達這個頂點我們作為結束，第一件事，我們先得知道每一道工序它要花多少天的時間完成，所以我們先把持續時間給標出來，這些邊之間的關係是什麼意思呢？

我如果想4到6，4到7這兩個組開工，它必須要等到1到4，2到4這兩個組全部完工，它們倆才開始接著往下走，有一種情況，可能更複雜一點，比如說4到6，4到7這兩個組要開工，它不僅要等1到4，2到4這兩個組結束，它還得等3到5這個組結束，就是這3個組要等齊了全部完工以後，4到6，4到7這兩個組才能開工，那我要怎麼辦呢？那你說這個答案不是很簡單嗎？我只要把4，5兩個頂點合併一下，都並上去不就好了,但是這種想法是不對的，你要看5到7這一個組它要開工跟1到4，2到4這兩個組是不是完工，一點關係沒有，5到7這個組關心的只是說前面3到5這個組，什麼時候完成，它完成了，5到7就可以走，但是呢，4到6和4到7這兩個組非要等到3到5，1到4，2到4它們一起才能走，這個時候這個圖要怎麼畫呢？

我們一個解決方法，就是畫一條虛邊，這條虛邊權重或者說持續時間我們把它定義成0，我如果這個圖這麼一畫的話，說明這兩道工序必須要等齊了，這3個任務全完工了以後，它們才可以往下走，而對於5到7這道工序來說，它只需要等到前一個工序3到5完工它就可以往下走了，這個就是我們AOE網路，有了這個AOE網路之後，我們想問的第一個問題，整個工期有多長呢？

這件事情要怎麼做呢？我們就要從頭開始，從一開始，第0天，因為這道工序要花6天的時間完成，所以這個頂點最早完成時間就是在第6天(0到1這個路徑)，

那同理因為這道工序說是要4天完成(0到2），所以這個頂點的最早完成時間是在第4天，3這個頂點最早完成時間是在第5天(0到3),到了3這個頂點以後，這又進入了下一個組，下一個組只需要兩天的時間(3到5),所以到達5這個頂點的最早完成時間就是7天，到了中間4這個頂點的時候，問題就來了，中間4這個頂點是要等齊了3個組才能往下走，即1到4，2到4，3到5，這3個組，沿著0->1->4這條路徑過來就是6天+1天，就是7天可以完成，沿著0->2->4過來就是4天+1天，5天就可以完成，沿著0->3->5->4過來呢，7天加0天，也是7天，所以在4這個結點會得到3個數字，一個7，一個5，還有一個7，最後我們應該把什麼數字填在這呢？得填最大的數字，因為我們要求的是把所有的3個組都等齊了才往下走，所以最早完成時間應該是所有數字裡面最大的那個，

於是也就導出了我們的一個遞推公式，我們首先初始化Earliest[0],初始點的最少完成時間，我們把它初始化為0，然後每次往後面遞推的時候，Earliest[j]都是等於什麼呢，它的前一步如果<i,j>是等於一條邊的話，都是前一步的Earliest的值(即Earliest[i])加上這條邊的權重，是應該等於下一個頂點它的Earliest(即Earliest[j]),

當這個時間不唯一的時候(即上面說的0->1->4,0->2->4,0->3->5這3條路徑)，就是有3條邊同時指向它，那麼我們應該取什麼呢？我們應該取所有邊裡面最大的那個，

這個就是我們整個工期的推算，就按照這個方法一直往下推到最後一個結束的頂點，我們就知道了整個的工期，是18天

解答見圖即可，整個工期在18天就可以結束，那麼什麼叫機動時間呢，這是我們的第二個問題，比如說，作為一個項目的負責人，你當然看這個圖想知道，哪幾個組是比較辛苦的，一天都不能耽誤的，哪幾個組是中間可以扔出去干別的事情的，也就是哪幾個組有機動時間，這個事情要怎麼做呢？就是我要保證整個工期要在18天結束，就是最晚開始時間，也得是18天的情況下，反推回去，看前面一個頂點，最晚哪天開始就可以，那麼從這個結束的頂點往回推，因為這個組需要2天完工(6->8這條路徑)，所以如果要在第18天時間結束的話，它無論如何得是從第16的時候開始，所以最晚開始時間要是第16天，7->8這個組呢，它是18天倒推回去，最晚也得是第14天開始，到4這個結點的時候，其實我們是有兩種選擇的，只不過例子裡面這兩種選擇剛好是一樣的，結點6反推到結點4(16減去9),結點7反推到結點4(14減去7），所以4這個結點最遲也得第7天的時候到位，再看一下反推7->5這個路徑，這個組只需要4天就可以完工，所以5這個結點只要在第10天的時候就可以完工，但是不行，為什麼不行呢？因為畫虛線的0這條邊還在這，因為4這個組還在這等，它要在第7天的時候必須要開工(也就是4這個結點)，否則整個工期就要延誤了，所以就意味著5這個結點也是第7天要完工，也是不可以延遲的，那這個故事告訴我們當我有兩種選擇的時候，我從7->5這條路徑倒推回來，其實第10天的時候開工就可以，但是從4->5這條路徑倒推回來，它必須要在第7天的時候完工，當我有兩種選擇的時候，必須選擇最小的，所以就有了我們的倒推公式，是從最後一個頂點開始的，最後一個頂點的Latest應該是等於它的Earliest(Earliest[8] == Latest[8] == 18),然後倒著往回推，如果i和j之間是有一條邊的話，那麼我應該是j這個結點的latest減去邊的權重，也就是它的持續時間，我就反推得到i最遲開始的時間，但是當我有多種選擇的時候，我應該選擇minmum, 選擇最小的

藍色為正向，紅色為負向，那什麼叫機動時間呢？機動時間就是有哪些組是不用一直趕工，比如說0->2這個組，它最早在第0天的時候就啟動了，它最晚在6天的時候完工就可以了(就是2這個結點),它只需要4天完成就可以了，它其實是有2天的時間是機動的，當然你放心，老闆是不會給他放假的2333,還有哪些組是有機動時間的呢？那我們的機動時間計算公式其實如果就是i到j之間如果有一條邊的話，那麼應該是j的終點，它的Latest減去起點的Earliest,然後再減去這個組的要花的時間，得到的這個值就是它的機動時間，按照這個公式去計算

我們會發現哪裡還會有機動時間，2->4這個結點(2)有機動時間，還有5->7這個組有機動時間,即5這個結點，7這個結點最遲第14天結束，5這個結點最早第7天就可以開始了，中間差了7天，而它只需要4天的時間去做，所以它的機動時間是3天，有了這個圖以後，整個項目的manager就可以根據這個圖來調度人手，那回到最初的關鍵路徑，關鍵路徑就是整個manager最需要關注的那些組，哪些組是一天都不能耽誤的，只要它耽誤一天，整個工期都得往後耽誤，關鍵路徑就指的是絕對不允許延誤的這些活動，也就是這些邊組成的路徑，叫作整個項目的關鍵路徑，那在這個圖裡面，其實關鍵路徑其實不止一條，沒有機動時間的那些組，從頭走到尾，那些任務組成的路徑就叫做關鍵路徑，那麼關鍵路徑的程序要怎麼寫呢？這個程序寫起來略煩，但是其實你要回答第一個問題的時候，這個程序其實還是比較簡單的，你要想知道整個工期有多長，其實你只需要把拓撲排序的程序，稍微改一改，就可以解決這個問題了。