圖的常見(jiàn)應(yīng)用

1、本節(jié)主要內(nèi)容： 1、最小生成樹(shù)算法 2、最短路徑 3、拓?fù)渑判?4、關(guān)鍵路徑19.5 最小生成樹(shù)1.基本概念 一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖，它包含原圖中的所有n個(gè)頂點(diǎn)，并且有保持圖連通的最少的邊。 （1）若在生成樹(shù)中刪除一條邊就會(huì)使該生成樹(shù)因變成非連通圖而不再滿足生成樹(shù)的定義；（2）若在生成樹(shù)中增加一條邊就會(huì)使該生成樹(shù)中因存在回路而不再滿足生成樹(shù)的定義；（3）一個(gè)連通圖的生成樹(shù)可能有許多；（4）有n個(gè)頂點(diǎn)的無(wú)向連通圖，無(wú)論它的生成樹(shù)的形狀如何，一定有且只有n-1條邊。 21V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)無(wú)向圖和它的

2、不同的生成樹(shù) 3 如果無(wú)向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，我們稱(chēng)這棵生成樹(shù)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱(chēng)最小生成樹(shù)。 構(gòu)造有n個(gè)頂點(diǎn)的無(wú)向連通帶權(quán)圖的最小生成樹(shù)必須滿足以下三條：（1）構(gòu)造的最小生成樹(shù)必須包括n個(gè)頂點(diǎn)；（2）構(gòu)造的最小生成樹(shù)中有且只有n-1條邊；（3）構(gòu)造的最小生成樹(shù)中不存在回路。 典型的構(gòu)造方法有兩種，一種稱(chēng)作普里姆（Prim）算法，另一種稱(chēng)作克魯斯卡爾（Kruskal）算法。 42.普里姆算法 一、算法思想 假設(shè)G=(V,E)為一個(gè)帶權(quán)圖，其中V為帶權(quán)圖中頂點(diǎn)的集合，E為帶權(quán)圖中邊的權(quán)值集合。設(shè)置兩個(gè)新的集合U和T，其中U用于存放帶權(quán)圖G的

3、最小生成樹(shù)的頂點(diǎn)的集合，T用于存放帶權(quán)圖G的最小生成樹(shù)的權(quán)值的集合。 普里姆算法思想是：令集合U的初值為U=u0（即假設(shè)構(gòu)造最小生成樹(shù)時(shí)從頂點(diǎn)u0開(kāi)始），集合T的初值為T(mén)=。從所有頂點(diǎn)uU和頂點(diǎn)vV-U的帶權(quán)邊中選出具有最小權(quán)值的邊(u,v)，將頂點(diǎn)v加入集合U中，將邊(u,v) 加入集合T中。如此不斷重復(fù)，當(dāng)U=V時(shí)則最小生成樹(shù)構(gòu)造完畢。此時(shí)集合U中存放著最小生成樹(shù)頂點(diǎn)的集合，集合T中存放著最小生成樹(shù)邊的權(quán)值集合。 56圖9-10 普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程 7圖9-10 普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程 8圖9-10 普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程 93.克魯斯卡爾算法 克魯斯卡爾算法是

4、一種按照帶權(quán)圖中邊的權(quán)值的遞增順序構(gòu)造最小生成樹(shù)的方法。設(shè)無(wú)向連通帶權(quán)圖G=(V,E)，其中V為頂點(diǎn)的集合，E為邊的集合。 克魯斯卡爾算法思想是：設(shè)帶權(quán)圖G的最小生成樹(shù)T由頂點(diǎn)集合和邊的集合構(gòu)成，其初值為T(mén)=(V,)，即初始時(shí)最小生成樹(shù)T只由帶權(quán)圖G中的頂點(diǎn)集合組成，各頂點(diǎn)之間沒(méi)有一條邊。這樣，最小生成樹(shù)T中的各個(gè)頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值遞增的順序考察帶權(quán)圖G中的邊集合E中的各條邊，若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊加入到最小生成樹(shù)T，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察的邊的兩個(gè)頂點(diǎn)屬于T的同一個(gè)連通分量，則將此邊舍去。如此下去，當(dāng)T中的

5、連通分量個(gè)數(shù)為1時(shí)，T中的該連通分量即為帶權(quán)圖G的一棵最小生成樹(shù) 10克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程 11克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程 12139.6 最短路徑 1.基本概念 路徑長(zhǎng)度:一條路徑上所經(jīng)過(guò)的邊的數(shù)目 帶權(quán)路徑長(zhǎng)度:路徑上所經(jīng)過(guò)邊的權(quán)值之和最短路徑:(帶權(quán))路徑長(zhǎng)度(值)最小的那條路徑圖9-13 （a）有向帶權(quán)圖； （b）鄰接矩陣 14152.從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑 一、狄克斯特拉算法思想 按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生最短路徑。 狄克斯特拉算法的思想是：設(shè)置兩個(gè)頂點(diǎn)的集合S和T，集合S中存放已找到最短路徑的頂點(diǎn)，集合T中存放當(dāng)前還未找到最短路徑的頂點(diǎn)。初始狀態(tài)時(shí)

6、，集合S中只包含源點(diǎn)，設(shè)為v0，然后從集合T中選擇到源點(diǎn)v0路徑長(zhǎng)度最短的頂點(diǎn)u加入到集合S中，集合S中每加入一個(gè)新的頂點(diǎn)u都要修改源點(diǎn)v0到集合T中剩余頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度值，集合T中各頂點(diǎn)的新的當(dāng)前最短路徑長(zhǎng)度值，為原來(lái)的當(dāng)前最短路徑長(zhǎng)度值與從源點(diǎn)過(guò)頂點(diǎn)u到達(dá)該頂點(diǎn)的路徑長(zhǎng)度中的較小者。此過(guò)程不斷重復(fù)，直到集合T中的頂點(diǎn)全部加入到集合S中為止。 16EFDBCA51810715EFDBCA530(a)EFDBCA530715EFDBCA5301810715EFDBCA851810715EFDBCA8510715(b)(c)(d)(e)(f)狄克斯特拉算法求從頂點(diǎn)A到其余各頂點(diǎn)最短路徑的過(guò)

7、程 173.每對(duì)頂點(diǎn)之間的最短路徑 帶權(quán)有向圖，每對(duì)頂點(diǎn)之間的最短路徑可通過(guò)調(diào)用狄克斯特拉算法實(shí)現(xiàn)。具體方法是：每次以不同的頂點(diǎn)作為源點(diǎn)，調(diào)用狄克斯特拉算法求出從該源點(diǎn)到其余頂點(diǎn)的最短路徑。重復(fù)n次就可求出每對(duì)頂點(diǎn)之間的最短路徑。由于狄克斯特拉算法的時(shí)間復(fù)雜度為O(n2)，所以這種算法的時(shí)間復(fù)雜度為O(n3)。 弗洛伊德算法的思想是：設(shè)矩陣cost用來(lái)存放帶權(quán)有向圖G的權(quán)值，即矩陣元素costij中存放著下標(biāo)為i的頂點(diǎn)到下標(biāo)為j的頂點(diǎn)之間的權(quán)值，可以通過(guò)遞推構(gòu)造一個(gè)矩陣序列A0,A1,A2,AN來(lái)求每對(duì)頂點(diǎn)之間的最短路徑。其中，Akij（0kn）表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)下標(biāo)

8、不大于k的最短路徑長(zhǎng)度。初始時(shí)有，A0ij=costij。18有向無(wú)環(huán)圖及其應(yīng)用 1 有向無(wú)環(huán)圖的概念 2 AOV網(wǎng)與拓?fù)渑判?3 AOE圖與關(guān)鍵路徑191 有向無(wú)環(huán)圖的概念 一個(gè)無(wú)環(huán)的有向圖稱(chēng)做有向無(wú)環(huán)圖（directed acycline praph）。簡(jiǎn)稱(chēng)DAG圖。DAG圖是一類(lèi)較特殊的有向圖，下圖給出了有向樹(shù)、DAG圖和有向圖的例子。20(1) 有向無(wú)環(huán)圖是描述含有公共子式的表達(dá)式的有效工具： 例如下述表達(dá)式： (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第六章討論的二叉樹(shù)來(lái)表示，如下圖所示。21 仔細(xì)觀察該表達(dá)式，可發(fā)現(xiàn)有一些相同的子表達(dá)式，如(c+d)和

9、(c+d)*e等，在二叉樹(shù)中，它們也重復(fù)出現(xiàn)。若利用有向無(wú)環(huán)圖，則可實(shí)現(xiàn)對(duì)相同子式的共享，從而節(jié)省存儲(chǔ)空間。例如下圖所示為表示同一表達(dá)式的有向無(wú)環(huán)圖。22(2)無(wú)環(huán)圖是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程的有效工具： 除最簡(jiǎn)單的情況之外，幾乎所有的工程（project）都可分為若干個(gè)稱(chēng)作活動(dòng)（activity）的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開(kāi)始必須在另一些子工程完成之后。 對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問(wèn)題：一是工程能否順利進(jìn)行：二是估算整個(gè)工程完成所必須的最短時(shí)間。我們也在這一節(jié)討論這一問(wèn)題。232 AOV網(wǎng)與拓?fù)渑判?AOV網(wǎng) (頂點(diǎn)表示活動(dòng)的網(wǎng))

10、(1) AOV概念：頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)之間存在的制約關(guān)系網(wǎng)稱(chēng)為AOV。(2) 用AOV表示一個(gè)工程： 概念所有的工程或者某種流程可以分為若干個(gè)小的工程或階段，這些小的工程或階段就稱(chēng)為活動(dòng)。若以圖中的頂點(diǎn)來(lái)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，則這樣活動(dòng)在頂點(diǎn)上的有向圖稱(chēng)為AOV網(wǎng)。在AOV網(wǎng)中，若從頂點(diǎn)i到頂點(diǎn)j之間存在一條有向路徑，稱(chēng)頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，或者稱(chēng)頂點(diǎn)j是頂點(diǎn)i 的后繼。若是圖中的弧，則稱(chēng)頂點(diǎn)i是頂點(diǎn)j的直接前驅(qū)，頂點(diǎn)j 是頂點(diǎn)i的直接后驅(qū)。249.7 拓?fù)渑判?1偏序關(guān)系和全序關(guān)系 拓?fù)渑判蚓褪且赡硞€(gè)集合上的偏序關(guān)系得到該集合上的全序關(guān)系。 若集合X上的關(guān)系R是自反

11、的、反對(duì)稱(chēng)的和傳遞的，則稱(chēng)關(guān)系R是集合X上的偏序關(guān)系（或稱(chēng)半序關(guān)系）。 設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對(duì)于每一個(gè)xX，都有(x,x)R，則稱(chēng)R是自反的。 設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，如果對(duì)于任意的x,y,zX，若當(dāng)(x,y)R且(y,z)R時(shí)，有(x,z)R，則稱(chēng)關(guān)系R是傳遞的。25偏序關(guān)系的實(shí)質(zhì) 是在集合X的元素之間建立層次結(jié)構(gòu)。這種層次結(jié)構(gòu)是依賴(lài)于偏序關(guān)系的可比性建立起來(lái)的。但是，偏序關(guān)系不能保證集合X中的任意兩個(gè)元素之間都能比較。而全序關(guān)系可以保證集合中的任意兩個(gè)元素之間都可以比較。26 對(duì)于AOV網(wǎng)的拓?fù)渑判蚓褪菍OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列。 拓?fù)渑判驅(qū)嶋H上就

12、是要由某個(gè)集合上的一個(gè)偏序關(guān)系得到該集合上的一個(gè)全序關(guān)系。 27下圖給出在一個(gè)AOV網(wǎng)上實(shí)施上述步驟的例子。28 例如：計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專(zhuān)業(yè)課才能畢業(yè)。29 4有向圖的拓?fù)渑判蛩惴?有向圖的拓?fù)渑判蛩惴ǎ?(1) 在有向圖中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并把它輸出； (2) 從有向圖中刪去該頂點(diǎn)以及與它相關(guān)的有向邊。 重復(fù)上述兩個(gè)步驟，直到所有頂點(diǎn)都輸出，或者剩余的頂點(diǎn)中找不到?jīng)]有前驅(qū)的頂點(diǎn)。在前一種情況下，頂點(diǎn)的輸出序列就是一個(gè)拓?fù)湫蛄?；后一種情況則說(shuō)明有向圖中存在回路，如果有向圖中存在回路，則該有向圖一定無(wú)法得到一個(gè)拓?fù)湫蛄小?0 上述算法僅能得到有向圖的一個(gè)拓?fù)湫蛄?/p>

13、。改進(jìn)上述算法，可以得到有向圖的所有拓?fù)湫蛄小?如果一個(gè)有向圖存在一個(gè)拓?fù)湫蛄?，通常表示該有向圖對(duì)應(yīng)的某個(gè)施工流程圖的一種施工方案切實(shí)可行；而如果一個(gè)有向圖不存在一個(gè)拓?fù)湫蛄?，則說(shuō)明該有向圖對(duì)應(yīng)的某個(gè)施工流程圖存在設(shè)計(jì)問(wèn)題，不存在切實(shí)可行的任何一種施工方案。 31 例：對(duì)于如下圖所示的AOV網(wǎng)，寫(xiě)出利用拓?fù)渑判蛩惴ǖ玫降囊粋€(gè)拓?fù)湫蛄小?解：根據(jù)拓?fù)渑判蛩惴?，得到的一個(gè)拓?fù)湫蛄袨?,1,7,2,4,8,5,9,3,6。392475608132建筑工程拓?fù)渑判騿?wèn)題 333 AOE圖與關(guān)鍵路徑1AOE網(wǎng)（邊表示活動(dòng)的網(wǎng)） (1) AOE網(wǎng)概念：若在帶權(quán)的有向圖中，以頂點(diǎn)表示事件，以有向邊表示活動(dòng)，邊

14、上的權(quán)值表示活動(dòng)的開(kāi)銷(xiāo)（如該活動(dòng)持續(xù)的時(shí)間），則此帶權(quán)的有向圖稱(chēng)為AOE網(wǎng)。 (2)AOE網(wǎng)表示一項(xiàng)工程能表示出： 完成預(yù)定工程計(jì)劃所需要進(jìn)行的活動(dòng); 每個(gè)活動(dòng)計(jì)劃完成的時(shí)間; 要發(fā)生哪些事件以及這些事件與活動(dòng)之間的關(guān)系;34(3) 通過(guò)AOE網(wǎng)可以求得： 估算工程完成的時(shí)間 確定哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵。 (4) AOE網(wǎng)的兩個(gè)特點(diǎn)： 只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動(dòng)才能開(kāi)始。 只有在進(jìn)入一某頂點(diǎn)的各有向邊所代表的活動(dòng)都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。35a9=6a6=4a2=7a1=5a3=3a4=6a5=3a7=5a8=4a10=5a11=8a

15、14=9a12=2a13=8a15=3 圖9-19 AOE網(wǎng)v0v3v1v4v7v6v8v5v2v936基本概念：路徑長(zhǎng)度：AOE網(wǎng)的一條路徑上所有活動(dòng)的總和稱(chēng)為該路徑的長(zhǎng)度。關(guān)鍵路徑：在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)的所有路徑中，具有最大路徑長(zhǎng)度的路徑稱(chēng)為關(guān)鍵路徑。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱(chēng)為關(guān)鍵活動(dòng)。顯然，完成整個(gè)工程的最短時(shí)間就是AOE網(wǎng)中關(guān)鍵路徑的長(zhǎng)度，也就是AOE網(wǎng)中各關(guān)鍵活動(dòng)所持續(xù)時(shí)間的總和。 例：找出前圖所示的AOE網(wǎng)中的關(guān)鍵路徑。解：在AOE網(wǎng)中，從源點(diǎn)v0到匯點(diǎn)v9共有13條路徑，分別計(jì)算這13條路徑的長(zhǎng)度，得到最大路徑長(zhǎng)度為31。最大路徑長(zhǎng)度對(duì)應(yīng)的關(guān)鍵路徑為(v0,v2,v3,

16、v4,v6,v9) 和(v0,v2,v3,v4,v7,v9)。373幾個(gè)參數(shù)的定義活動(dòng)的持續(xù)時(shí)間dut()：對(duì)于有向邊代表的活動(dòng)，dut()是該有向邊的權(quán)值。事件可能的最早開(kāi)始時(shí)間e(k)：對(duì)于頂點(diǎn)k代表的事件，e(k)是從源點(diǎn)到該頂點(diǎn)的最大路徑長(zhǎng)度。在一個(gè)有n+1個(gè)事件的AOE網(wǎng)中, 源點(diǎn)0的最早開(kāi)始時(shí)間e(0)等于0。事件k（k=1,2,3,n）可能的最早開(kāi)始時(shí)間e(k)可用遞推公式表示為： e(k)=0 頂點(diǎn)k=0為源點(diǎn)Max e(j)+dut() | 為網(wǎng)中的有向邊 其他頂點(diǎn)38活動(dòng)可能的最早開(kāi)始時(shí)間e(i)：對(duì)于有向邊ai代表的活動(dòng)，e(i)是該活動(dòng)的弧尾事件可能的最早發(fā)生時(shí)間。假設(shè)

17、活動(dòng)ai代表的是有向邊，即ai是關(guān)聯(lián)事件j和事件k的的活動(dòng)，則e(i) =e(j)。 活動(dòng)允許的最晚開(kāi)始時(shí)間l(i)：對(duì)于有向邊ai代表的活動(dòng)，l(i)是該活動(dòng)的弧頭事件允許的最晚發(fā)生時(shí)間減去該活動(dòng)持續(xù)的時(shí)間。l(i)是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai必須開(kāi)始的時(shí)間。假設(shè)活動(dòng)ai代表的是有向邊，即ai是關(guān)聯(lián)事件j和事件k的的活動(dòng)，則l(i) = l(k) - dut()。 這樣，每個(gè)活動(dòng)允許的時(shí)間余量就是l(i) - e(i)。而關(guān)鍵活動(dòng)就是l(i) - e(i) = 0的那些活動(dòng)，即可能的最早開(kāi)始時(shí)間e(i)等于允許的最晚開(kāi)始時(shí)間l(i)的那些活動(dòng)就是關(guān)鍵活動(dòng)。394尋找關(guān)鍵活動(dòng)的算法

18、 求AOE網(wǎng)中關(guān)鍵活動(dòng)的算法步驟為： （1）建立包含n+1個(gè)頂點(diǎn)、e條有向邊的AOE網(wǎng)。其中，頂點(diǎn)v0為源點(diǎn)，頂點(diǎn)vn為匯點(diǎn)； （2）根據(jù)有向圖的拓?fù)渑判蛩惴?，求出AOE網(wǎng)的拓?fù)湫蛄?。如果AOE網(wǎng)中存在環(huán)，拓?fù)湫蛄胁淮嬖?，則無(wú)法得到AOE網(wǎng)的關(guān)鍵活動(dòng)，算法失敗退出； （3）從源點(diǎn)v0開(kāi)始，令源點(diǎn)v0的最早開(kāi)始時(shí)間ve0=0，按拓?fù)湫蛄星笃溆喔黜旤c(diǎn)k(k=1,2,3,n)的最早開(kāi)始時(shí)間vek； （4）從匯點(diǎn)vn開(kāi)始，令匯點(diǎn)vn的最晚發(fā)生時(shí)間vln=ven，按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)k(k=n-1,n-2,2,1,0)的最晚發(fā)生時(shí)間vlk； （5）計(jì)算每個(gè)活動(dòng)的最早開(kāi)始時(shí)間ek (k=1,2,3,e

19、)； （6）計(jì)算每個(gè)活動(dòng)的最晚開(kāi)始時(shí)間lk (k=1,2,3,e)； （7）找出所有ek= lk的活動(dòng)k，這些活動(dòng)即為AOE網(wǎng)的關(guān)鍵活動(dòng)。40 下圖給出了一個(gè)具有15個(gè)活動(dòng)、11個(gè)事件的假想工程的AOE網(wǎng)。v1,v2, v11分別表示一個(gè)事件；,分別表示一個(gè)活動(dòng)；用a1,a2, ,a15代表這些活動(dòng)。其中,v1稱(chēng)為源點(diǎn)，是整個(gè)工程的開(kāi)始點(diǎn)，其入度為0；v11為終點(diǎn)，是整個(gè)工程的結(jié)束點(diǎn)，其出度為0 。 對(duì)于AOE網(wǎng)，可采用與AOV網(wǎng)一樣的鄰接表存儲(chǔ)方式。其中，鄰接表中邊結(jié)點(diǎn)的域?yàn)樵撨叺臋?quán)值，即該有向邊代表的活動(dòng)所持續(xù)的時(shí)間。415、求關(guān)鍵路徑的過(guò)程 下面以前圖所示的AOE網(wǎng)為例，求出上述參量，來(lái)

20、確定該網(wǎng)的關(guān)鍵活動(dòng)和關(guān)鍵路徑。 (1) 按照式6-1求事件的最早發(fā)生時(shí)間vek ve 1=0 ve 2=3 ve 3=4 ve 4=ve2+2=5 ve 5=maxve2+1,ve3+3=7 ve 6=ve3+5=9 ve 7=maxve4+6,ve5+8=15 ve 8=ve5+4=11 ve 9=maxve8+10,ve6+2=21 ve 10=maxve8+4,ve9+1=22 ve 11=maxve7+7,ve10+6=2842(2) 按照式6-2求事件的最遲發(fā)生時(shí)間vlk。 vl 11= ve 11=28 vl 10= vl 11-6=22 vl 9= vl 10-1=21 vl 8

21、=min vl 10-4, vl 9-10=11 vl 7= vl 11-7=21 vl 6= vl 9-2=19 vl 5=min vl 7-8,vl 8-4=7 vl 4= vl 7-6=15 vl 3=min vl 5-3, vl 6-5=4 vl 2=min vl 4-2, vl 5-1=6 vl 1=minvl 2-3, vl 3-4=043 (3) 按照 (6-3)式和(6-4)式求活動(dòng)ai的最早開(kāi)始時(shí)間ei和最晚開(kāi)始時(shí)間li活動(dòng)a1 e 1=ve 1=0 l 1=vl 2 -3 =3活動(dòng)a2 e 2=ve 1=0 l 2=vl 3 - 4=0活動(dòng)a3 e 3=ve 2=3 l 3

22、=vl 4 - 2=13活動(dòng)a4 e 4=ve 2=3 l 4=vl 5 - 1=6活動(dòng)a5 e 5=ve 3=4 l 5=vl 5 - 3=4活動(dòng)a6 e 6=ve 3=4 l 6=vl 6 - 5=14活動(dòng)a7 e 7=ve 4=5 l 7=vl 7 - 6=15活動(dòng)a8 e 8=ve 5=7 l 8=vl 7 - 8=13活動(dòng)a9 e 9=ve 5=7 l 9=vl 8 - 4=7活動(dòng)a10 e 10=ve 6=9 l 10=vl 9 - 2=19活動(dòng)a11 e 11=ve 7=15 l 11=vl 11 - 7=21活動(dòng)a12 e 12=ve 8=11 l 12=vl 10 - 4=18活動(dòng)a13 e 13=ve 8=11 l 13=vl 9 - 10=11活動(dòng)a14 e 14=ve 9=21 l 14=vl 10 -1=21活動(dòng)a15 e 15=ve 10=22 l 15=vl 11 -6 =2244(5) 求關(guān)鍵路徑： 比較ei和li