AOE網與關鍵路徑簡介

前面我們說過的拓撲排序主要是為解決一個工程能否順序進行的問題，但有時我們還需要解決工程完成需要的最短時間問題。如果我們要對一個流程圖獲得最短時間，就必須要分析它們的拓撲關系，并且找到當中最關鍵的流程，這個流程的時間就是最短時間。

在前面講了AOV網的基礎上，來介紹一個新的概念。在一個表示工程的帶權有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權值表示活動的持續時間，這種有向圖的邊表示活動的網，稱之為AOE網（Activity On edge Network)。由于一個工程，總有一個開始，一個結束，在正常情況下，AOE網只有一個源點一個匯點。

既然AOE網是表示工程流程的，所以就具有明顯的工程屬性。只有在某頂點代表的事件發生后，從該頂點出發的各活動才能開始。只有在進入某頂點的各活動都已經結束，該頂點代表的事件才能發生。

盡管AOV網和AOE網都是用來對工程建模的，但它們還是有很大的區別，主要體現在AOV網是頂點表示活動的網，它只描述活動之間的制約關系，而AOE網是用邊表示活動的網，邊上的權值表示活動持續的時間，如圖7-9-3所示兩圖的對比。因此，AOE網是要建立在活動之間制約關系沒有矛盾的基礎之上，再來分析完成整個工程需要多少時間，或者為縮短完成工程所需時間，應當加快哪些活動等問題。

我們把路徑上各個活動所持續的時間之后稱為路徑長度，從源點到匯點具有最大長度的路徑叫關鍵路徑，在關鍵路徑上完成的活動叫關鍵活動。顯然就圖7-9-3的AOE網而言，開始->發動機完成->部件集中到位->組裝完成就是關鍵路徑，路徑長度為5.5。

如果我們需要縮短整個工期，去改進輪子的生產效率，哪怕改動成0.1也無益于整個工期的變化，只有縮短關鍵路徑上的關鍵活動時間才才可以減少整個工期長度。例如如果發動機制造縮短為2.5，整車組裝縮短為1.5，那么關鍵路徑就為4.5，整整縮短了一天的時間。

如果某項活動的最早開始時間和最晚開始時間一樣，表示中間沒有空隙，則此項活動就為關鍵活動。為此，我們需要定義以下幾個參數。

1、事件的最早發生時間 etv（earliest time of vertex）：即頂點vk 的最早發生時間。

2、事件的最晚發生時間 ltv（latest time of vertex）：即頂點vk 的最短發生時間。也就是每個頂點對應的事件最晚需要開始的時間，超出此時間將會延誤整個工期。

3、活動的最早開工時間 ete （earliest time of edge）：即弧ak 的最早發生時間。

4、活動的最晚開工時間 lte （latest time of edge ）：即弧ak 的最晚發生時間，也就是不推遲工期的最晚開工時間。

我們首先求得1和2，而 ete 本來是表示活動<vk, vj> 的最早開工時間，是針對弧來說的，但只有此弧的弧尾頂點vk的事件發生了，它才可以開始，因此ete = etv[k]。

而lte 表示的是活動<vk, vj> 的最晚開工時間，但此活動再晚也不能等vj 事件發生才開始，所以lte = ltv[j] - len<vk, vj> 。

最終，我們再來判斷ete 和 lte 是否相等，相等意味著活動沒有任何空閑，是關鍵路徑，否則就不是。

現在來談談如何求etv 和 ltv。

假設我們現在已經求得頂點v0對應的 etv[0] = 0,頂點v1對應的etv[1] = 3, 頂點v2對應的etv[2] = 4, 現在我們需要求頂點v3對應的etv[3]，其實就是求etv[1] + len<v1, v3> 與 etv[2] + len<v2, v3> 的較大值。顯然 3+5 < 4+8, 得到etv[3] = 12, 如圖7-9-5所示。

由此我們也可以得出計算頂點vk的最早發生時間即求etv[k]的公式是：

其中P[k] 表示所有到達頂點vk的弧的集合。比如圖7-9-5的P[3]就是<v1, v3> 和 <v2, v3> 兩條弧。len<vi, vk> 是弧<vi, vk>上的權值。

假如我們現在已經求得v9~ v5 頂點的ltv值，現在要求v4 的ltv 值，由鄰接表可得到v4 有兩條弧<v4, v6>, <v4, v7>，可以得到

ltv[4] = min(ltv[7] - 4, ltv[6] - 9) = 15，如圖7-9-8所示。

可以發現，在計算ltv時，其實是把拓撲序列倒過來進行而已，因此可以得到計算頂點vk最晚發生時間即求ltv[k] 的公式是：

其中S[K]表示所有從頂點vk出發的弧的集合。比如圖7-9-8的S[4] 就是<v4, v6>和<v4, v7>兩條弧，len<vk, vj> 是弧<vk, vj> 上的權值。

現有一AOE網圖如圖7-9-4所示，我們使用鄰接表存儲結構，注意與拓撲排序時鄰接表結構不同的地方在于，這里弧表結點增加了weight域，用來存儲弧的權值。

求解事件的最早發生時間etv的過程，就是我們從頭至尾找拓撲序列的過程，因此在求關鍵路徑之前，需要先調用一次拓撲序列算法的代碼來計算etv 和拓撲序列列表，我們針對前面講過的AOV網與拓撲排序的程序進行改進，代碼如下（參考《大話數據結構》）：

C++ Code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/*?拓撲排序，若GL無回路，則輸出拓撲排序序列并返回1，若有回路返回0。?*/
bool?TopologicalSort(GraphAdjList?GL)
{
????EdgeNode?*pe;
????int?i,?k,?gettop;
????int?top?=?0;/*?用于棧指針下標??*/
????int?count?=?0;/*?用于統計輸出頂點的個數??*/
????/*?建棧將入度為0的頂點入棧??*/
????int?*stack?=?(int?*)malloc(GL->numVertexes?*?sizeof(int));

????for?(i?=?0;?i?<?GL->numVertexes;?i++)
????????if?(0?==?GL->adjList[i].in)
????????????stack[++top]?=?i;/*?將入度為0的頂點入棧?*/

????top2?=?0;
????etv?=?(int?*)malloc(GL->numVertexes?*?sizeof(int));
????for?(i?=?0;?i?<?GL->numVertexes;?i++)
????????etv[i]?=?0;?/*?初始化?*/
????stack2?=?(int?*)malloc(GL->numVertexes?*?sizeof(int));

????cout?<<?"TopologicalSort?..."?<<?endl;

????while?(top?!=?0)
????{
????????gettop?=?stack[top--];
????????cout?<<?GL->adjList[gettop].data?<<?"?->?";
????????count++;??/*?輸出i號頂點，并計數?*/

????????stack2[++top2]?=?gettop;?/*?將彈出的頂點序號壓入拓撲序列的棧?*/

????????for?(pe?=?GL->adjList[gettop].firstedge;?pe;?pe?=?pe->next)
????????{
????????????k?=?pe->adjvex;
????????????/*?將i號頂點的鄰接點的入度減1，如果減1后為0，則入棧?*/
????????????if?(!(--GL->adjList[k].in))
????????????????stack[++top]?=?k;
????????????/*?求各頂點事件的最早發生時間etv值?*/
????????????if?((etv[gettop]?+?pe->weight)?>?etv[k])
????????????????etv[k]?=?etv[gettop]?+?pe->weight;
????????}
????}
????cout?<<?endl;
????if?(count?<?GL->numVertexes)
????????return?false;
????else
????????return?true;
}

在程序開始處我們聲明了幾個全局變量：

int *etv,*ltv; /* 事件最早發生時間和最遲發生時間數組，全局變量 */
int *stack2; ? /* 用于存儲拓撲序列的棧 */
int top2; ? /* 用于stack2的指針 */

其中stack2用來存儲拓撲序列，以便后面求關鍵路徑時使用。

上面的拓撲排序函數中除了增加了第12～19行，29行，38～39行，其他跟前面講過的AOV網與拓撲排序沒什么區別。

第12～19行初始化全局變量etv數組、top2和stack2的過程。第29行就是將本來要輸出的拓撲序列壓入全局棧stack2中。第38～39行很關鍵，是求etv數組的每一個元素的值，具體求值辦法參見AOE網和關鍵路徑。

下面來看求關鍵路徑的算法代碼。

C++ Code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/*?求關鍵路徑,GL為有向網，輸出G的各項關鍵活動?*/
void?CriticalPath(GraphAdjList?GL)
{
????EdgeNode?*pe;
????int?i,?j,?k,?gettop;
????int?ete,?lte;/*?聲明活動最早發生時間和最遲發生時間變量?*/
????TopologicalSort(GL);/*?求拓撲序列，計算數組etv和stack2的值?*/

????ltv?=?(int?*)malloc(GL->numVertexes?*?sizeof(int));?/*?事件最早發生時間數組?*/

????for?(i?=?0;?i?<?GL->numVertexes;?i++)
????????ltv[i]?=?etv[GL->numVertexes?-?1];/*?初始化?*/

????cout?<<?"etv?:??";
????for?(i?=?0;?i?<?GL->numVertexes;?i++)
????????cout?<<?etv[i]?<<?'?';
????cout?<<?endl;

????while?(top2?!=?0)/*?出棧是求ltv?*/
????{
????????gettop?=?stack2[top2--];
????????/*?求各頂點事件的最遲發生時間ltv值?*/
????????for?(pe?=?GL->adjList[gettop].firstedge;?pe;?pe?=?pe->next)
????????{
????????????k?=?pe->adjvex;
????????????if?(ltv[k]?-?pe->weight?<?ltv[gettop])
????????????????ltv[gettop]?=?ltv[k]?-?pe->weight;
????????}
????}

????cout?<<?"ltv?:??";
????for?(i?=?0;?i?<?GL->numVertexes;?i++)
????????cout?<<?ltv[i]?<<?'?';
????cout?<<?endl;
????/*?求ete,lte和關鍵活動?*/
????for?(j?=?0;?j?<?GL->numVertexes;?j++)
????{
????????for?(pe?=?GL->adjList[j].firstedge;?pe;?pe?=?pe->next)
????????{
????????????k?=?pe->adjvex;
????????????ete?=?etv[j];/*?活動最早發生時間?*/
????????????lte?=?ltv[k]?-?pe->weight;/*?活動最遲發生時間?*/
????????????if?(ete?==?lte)?/*?兩者相等即在關鍵路徑上?*/
????????????????cout?<<?"<v"?<<?GL->adjList[j].data?<<?"?-?v"
?????????????????????<<?GL->adjList[k].data?<<?">?length:?"?<<?pe->weight?<<?endl;
????????}
????}
}

函數第7行調用求拓撲序列的函數，執行完畢后，全局數組etv和棧stack2 如圖7-9-6所示，top2 = 10，也就是說，對于每個事件的最早發生時間，我們已經計算出來了。