選擇題快速求解AOE網的關鍵路徑

#引言

求解AOE網關鍵路徑時，書上的方法為先從源點到彙點求解事件最早發生時間ve，再從彙點到源點求解事件最遲發生時間vl，再利用ve和vl求解每個活動的最早開始時間e(i)和最遲開始時間l(i)，e(i)和l(i)相等的活動則為關鍵活動，關鍵活動組成的從源點到彙點的路徑即為關鍵路徑。

王道的書上在AOE的部分，備注了一小行話：“如果這是一道選擇題，根據上述求ve()的過程就已經能知道關鍵路徑。”，但并沒有展開講如何确定。本文就補充說明一下。

#求法

這裡直接舉例給出求法

如下AOE圖

我們從V1開始依次求解事件的最早發生時間ve，前三個頂點答案很顯然，求得如下

V1	V2	V3	V4	V5	V6
ve()	3	2

在求解V4的時候，需要對兩條路徑進行比較，即ve(4)=Max{ve(2)+a3,ve(3)+a5}=Max{5,6}，顯然選取的是a5這條路徑。

這意味着a3這條路徑對V4來講是"備援的"，或者說因為a5的存在，它有可以改變的空間。也就是a3一定不是關鍵路徑。我們可以叉掉它。

按照以上思路，我們完成ve()的求解，并叉掉那些比較時被比下去的路徑。 最後得到：

直覺一點，我們把這些路徑都去掉：

上圖中，V1是源點，V6是彙點，完成工程意味着 V1到V6的一條路徑，而去掉“不關鍵”的路徑（活動邊）後 還可以走通的路徑就是關鍵路徑。 即上圖中的(V1,V3,V4,V6)或者說(a2,a5,a7) （注：a1和a4雖然保留在圖中，但并不是關鍵活動，因為他們不在關鍵路徑上）

再舉個多條關鍵路徑情況的例子，我們從V1開始依次計算ve()。

V1	V2	V3	V4	V5	V6
ve()	Max{3,ve(3)+4}	8

計算到V2時，比較兩條路徑，淘汰路徑a，ve(2)=12

V1	V2	V3	V4	V5	V6
ve()	12	8	21	Max{ve(3)+10,ve(2)+6}

計算到V5時，兩條路徑消耗是相同的！這時候兩條路徑都保留下來，他們都有可能成為關鍵路徑。

V1	V2	V3	V4	V5	V6
ve()	12	8	21	18	Max{ve(5)+9,ve(4)+6}

計算到V6時也一樣，兩條路徑的消耗相同，都保留。

最終結果是隻去掉了路徑a：

則此時源點V1到彙點V6的路徑，即原圖中的關鍵路徑有三條：

1. bfh
2. bdeh
3. bdcg