上篇博客我們介紹了AOV網(wǎng)的拓撲序列，請參考《數(shù)據(jù)結(jié)構(gòu)(七) AOV網(wǎng)的拓撲排序(Swift面向?qū)ο蟀?》。拓撲序列中包括項目的每個結(jié)點，沿著拓撲序列將項目進行下去是肯定可以將項目完成的，但是工期不是最優(yōu)的。因為拓撲序列是一個串行序列，如果按照該序列執(zhí)行項目，那么就是串行執(zhí)行的。我們知道在一個項目中的一些子工程是可以并行來完成的，這也就類似我們的多線程。今天我們要解決的問題就是找出一個關(guān)鍵路徑，是工期最優(yōu)并保證工程的完成。什么是關(guān)鍵路徑，我們在下方會進行詳細介紹。
一、關(guān)鍵路徑概述
在聊關(guān)鍵路徑之前，我們先看一個簡單的實例，如下圖所示。我們將下方這個有向無環(huán)圖看做是整個工程，將每個節(jié)點看做是該項目工程的一個子工程。子工程間又有一定的優(yōu)先級。在下方圖中，A的優(yōu)先級最高。A做完后，B、C才可以進行開發(fā)。B、C完成后，我們才可以開發(fā)D。從下圖中我們不難看出，該圖的拓撲序列為A, B, C, D。如果我們按照串行的方式來完成此工程的話，那么工程完成的順序可以是A-5->B, A-8->C, B-3->D, C-10->D?？倳r間為26。
從上面這個序列中我們顯然可以看出來這不是最優(yōu)的，因為A->B, A->C可以同時進行，B->D和C->D也可以同時進行。在允許某些子工程同時進行的情況下，A->B和A-C可以同時進行，因為A->B所需時間小于A->C所需時間，所以我們選擇A->C。在A->C執(zhí)行這8個小時的時間里，A->B和B->D已經(jīng)執(zhí)行完了，就剩下C->D了，所以關(guān)鍵工期為A->C->D=18。
在求關(guān)鍵路徑的算法中，我們先求出每個事件的最早完成時間。在事件最早完成的時間集合中，工程最后一步完成的時間就是我們工程完成的最優(yōu)時間。然后在工程時間最優(yōu)的情況下求出每個事件最晚完成時間。如果某個時間最早的完成時間與最晚的完成時間相同，那么該事件就是我們的關(guān)鍵事件，該事件就位于我們關(guān)鍵路徑中。如果這樣敘述有些抽象，那么我們就拿下方這個簡單圖來做個類比。
在上方這個有向無環(huán)圖中，我們可以求出每個事件最早發(fā)生的時間。下方截圖就是每個事件所對應(yīng)的最早完成的事件，因為D是工程的尾結(jié)點，所以該工程完成的最早
