東南大學數(shù)據(jù)結(jié)構(gòu)_Lec010

1、第10講 圖的應(yīng)用最短路徑1數(shù)據(jù)結(jié)構(gòu)有向無環(huán)圖的應(yīng)用背景一個工程(project)都可分為若干個稱為活動(active)的子工程(或工序)，各個子工程受到一定的條件約束：某個子工程必須開始于另一個子工程完成之后；整個工程有一個開始點(起點)和一個終點。 人們關(guān)心的問題：工程能否順利完成?影響工程的關(guān)鍵活動是什么?估算整個工程完成所必須的最短時間是多少?有向無環(huán)圖(Directed Acycling Graph)是圖中沒有回路(環(huán))的有向圖。DAG是一類具有代表性的圖，主要用于研究工程項目的工序問題、工程時間進度問題等。數(shù)據(jù)結(jié)構(gòu)2AOV網(wǎng)在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間

2、的優(yōu)先關(guān)系，這樣的有向圖為頂點表示活動的網(wǎng) ，稱為AOV網(wǎng)(Activity On Vertex Network)。AOV網(wǎng)中的弧表示活動之間存在的某種制約關(guān)系；AOV網(wǎng)中不能存在回路。設(shè) G =(V, E)是一個具有n個頂點的有向圖，V中的頂點序列v1, v2, , vn，滿足若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。這樣的頂點序列為一個拓撲序列。拓撲排序就是對一個有向圖構(gòu)造拓撲序列的過程。輸出全部頂點，則說明是不存在環(huán)的AOV網(wǎng)；否則不是AOV網(wǎng)。解決一個工程能否順利進行的問題。數(shù)據(jù)結(jié)構(gòu)3拓撲排序算法 算法思想 在AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點（入度為0）且輸

3、出； 在AOV網(wǎng)中刪除該頂點，以及從該頂點出發(fā)(以該頂點為尾) 的所有弧 ； 重復、，直到圖中全部頂點都已輸出(圖中無環(huán))或圖中不存在無前驅(qū)的頂點(圖中必有環(huán))。 算法實現(xiàn) 采用正鄰接表作為AOV網(wǎng)的存儲結(jié)構(gòu)； 設(shè)立堆棧，用來暫存入度為0的頂點； 刪除頂點以它為尾的弧，即弧頭頂點的入度減1。數(shù)據(jù)結(jié)構(gòu)4拓撲排序過程有向圖的拓撲排序過程，其拓撲序列是： (v1,v6,v4,v3,v2,v5)數(shù)據(jù)結(jié)構(gòu)5v1v2v3v4v5v6(a) 有向圖有向圖(b) 輸出輸出v1后后v4v2v3v5v6(c) 輸出輸出v6后后v4v2v3v5(d) 輸出輸出v4后后v2v3v5(e) 輸出輸出v3后后v2v5AO

4、E網(wǎng)在一個表示工程的帶權(quán)有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權(quán)值表示活動的持續(xù)時間，這種用有向圖的邊表示活動的網(wǎng)，稱之為AOE網(wǎng)(Activity On Edge Network)。AOE網(wǎng)中沒有入邊的頂點稱為始點或源點，沒有出邊的頂點稱為終點或匯點；正常情況下，AOE網(wǎng)只有一個源點、一個匯點。數(shù)據(jù)結(jié)構(gòu)6v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2AOE網(wǎng)示例 v0是源點，表示一個工程的開始 v8是匯點，表示整個工程的結(jié)束AOV網(wǎng) VS AOE網(wǎng)AOV網(wǎng)與AOE網(wǎng)都是用來對工程

5、建模。AOV網(wǎng)只描述活動之間的制約關(guān)系；AOE網(wǎng)邊上的權(quán)值表示活動持續(xù)時間(建立在活動之間制約關(guān)系沒有矛盾的基礎(chǔ)上)。數(shù)據(jù)結(jié)構(gòu)7開始造外殼造發(fā)動機造輪子造底盤其它零部件集中組裝完成開始外殼完成發(fā)動機完成輪子完成底盤完成其它零部件部件集中到位完成230.5220.50.50.50.50.52AOV網(wǎng)AOE網(wǎng)與AOE有關(guān)的研究問題完成整個工程至少需要多少時間?（最短時間）哪些活動是影響工程進度(費用)的關(guān)鍵?路徑上各個活動所持續(xù)的時間之和稱為路徑長度，從源點到匯點具有最大長度的路徑叫關(guān)鍵路徑，在關(guān)鍵路徑上的活動叫關(guān)鍵活動。關(guān)鍵活動是影響整個工程的關(guān)鍵，只有縮短關(guān)鍵路徑上的關(guān)鍵活動時間才可以減少整個

6、工程的工期長度。如何找出關(guān)鍵路徑？數(shù)據(jù)結(jié)構(gòu)8關(guān)鍵路徑算法原理找到所有活動的最早開始時間和最晚開始時間，并且比較它們，如果相等就意味著此活動是關(guān)鍵活動，活動間的路徑為關(guān)鍵路徑。定義幾個參數(shù)：事件的最早發(fā)生時間etv (earliest time of vertex)：頂點vk的最早發(fā)生時間；事件的最晚發(fā)生時間ltv (latest time of vertex)：頂點vk的最晚發(fā)生時間，即對應(yīng)事件最晚需要開始的時間，超出此時間將會延誤整個工期；活動的最早開工時間ete (earliest time of edge)：弧ak的最早發(fā)生時間；活動的最晚開工時間lte(latest time of e

7、dge)：弧ak的最晚發(fā)生時間，即不推遲工期的最晚開工時間。數(shù)據(jù)結(jié)構(gòu)9關(guān)鍵路徑算法 算法思想 利用拓撲排序求出AOE網(wǎng)的一個拓撲序列； 從拓撲排序的序列的第一個頂點(源點)開始，按拓撲順序依次計算每個事件的最早發(fā)生時間etv(i) ； 除源點外，只有進入頂點 vj 的所有弧所代表的活動全部結(jié)束后，事件vj才能發(fā)生。即只有vj 的所有前驅(qū)事件vi的最早發(fā)生時間etv(i)計算出來后，才能計算etv(j) 。 從拓撲排序的序列的最后一個頂點(匯點)開始，按逆拓撲順序依次計算每個事件的最晚發(fā)生時間ltv(i) ；只有 vj 的所有后繼事件 vk 的最晚發(fā)生時間ltv(k)計算出來后，才能計算ltv(

8、j) 。數(shù)據(jù)結(jié)構(gòu)10求AOE中的關(guān)鍵路徑和關(guān)鍵活動1.拓撲排序的序列： (v0, v1, v2, v3, v4, v5, v6, v7, v8)；2.計算各個事件的etv(i)和ltv(i)的值（見下表）；3.關(guān)鍵路徑： (v0, v2, v4, v7 , v8) 和 (v0, v2, v5 , v7 , v8) ；4.關(guān)鍵活動： ， 。數(shù)據(jù)結(jié)構(gòu)11v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2頂頂點點v0v1v2v3v4v5v6v7v8etv(i) 0310122217202833ltv(i)

9、 0910232217312833第10講 圖的應(yīng)用有向無環(huán)圖及其應(yīng)用12數(shù)據(jù)結(jié)構(gòu)最短路徑問題若用帶權(quán)圖表示交通網(wǎng)，圖中頂點表示地點，邊代表兩地之間有直接道路，邊上的權(quán)值表示路程(或所花費用或時間) 。從一個地方到另一個地方的路徑長度表示該路徑上各邊的權(quán)值之和。 兩地之間是否有通路? 在有多條通路的情況下哪條最短?考慮到交通網(wǎng)的有向性，討論帶權(quán)有向圖的最短路徑問題，并稱路徑上的第一個頂點為源點，最后一個頂點為終點。兩種最常見的最短路徑問題：單源點的最短路徑每一對頂點之間的最短路徑數(shù)據(jù)結(jié)構(gòu)13單源點的最短路徑問題提出問題：給定帶權(quán)有向圖G和源點v，求從v到G中其余各頂點的最短路徑。迪杰斯特拉(D

10、ijkstra)提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法，即迪杰斯特拉(Dijkstra)算法。數(shù)據(jù)結(jié)構(gòu)14v0v5v4v3v2v11005106050203010帶權(quán)有向圖G源點終點最短路徑路徑長度v0v1無v2(v0 , v2)10v3(v0 , v4 , v3)50v4(v0 , v4)30v5(v0 , v4 , v3 , v5)60從v0到其余各頂點的最短路徑迪杰斯特拉(Dijkstra)算法思想引進一個輔助向量D，它的每個分量Di表示當前所找到的從源點v 到每個終點vi 的最短路徑的長度。它的初態(tài)：若從v 到vi 有弧，則Di為弧上的權(quán)值，否則置為。 長度為：Dj = Mi

11、n Di | viV 的路徑就是從v 出發(fā)的長度最短的一條最短路徑(v, vj )。假設(shè)下一條長度次短的最短路徑的終點是 vk ，則這條路徑或者是(v, vk )，或者是(v, vj , vk)。它的長度或者是從v 到vk 的弧上的權(quán)值，或者是Dj和從vj到vk 的弧上的權(quán)值之和。一般情況下，假設(shè)S為已求得最短路徑的終點的集合，可證明：下一條最短路徑(設(shè)其終點為x)或者是(v, x )，或者是中間只經(jīng)過S中的頂點而最后到達頂點x的路徑。(反證法) 下一條長度次短的最短路徑長度：Dj = Min Di | vi V-S Di或者是上的權(quán)值，或者是Dk(vkS)和上的權(quán)值之和。數(shù)據(jù)結(jié)構(gòu)15迪杰斯特

12、拉(Dijkstra)算法找到從源點到某一個特定的終點的最短路徑，和求源點到其他所有頂點的最短路徑一樣復雜，其時間復雜度都是O(n2) 。數(shù)據(jù)結(jié)構(gòu)16v0v5v4v3v2v11005106050203010 10 30 100 5 50 10 20 60 終點從v0到各終點的D值和最短路徑的求解過程i=1i=2i=3i=4i=5v1無v210(v0，v2)v360(v0, v2, v3)50(v0, v4, v3)v430(v0，v4)30(v0，v4)v5100(v0，v5)100(v0，v5)90(v0, v4, v5)60(v0, v4, v3, v5)vjv2v4v3v5Sv0, v2

13、v0, v2, v4v0, v2, v3, v4v0, v2, v3, v4, v5每一對頂點間的最短路徑辦法一：每次以一個頂點為源點，重復執(zhí)行Dijkstra算法 n次，可求得每一對頂點之間的最短路徑， 總的執(zhí)行時間為O(n3) 。辦法二：弗羅伊德(Floyd)提出了另一個算法： 弗羅伊德(Floyd)算法 其時間復雜度也是O(n3)，但形式上簡單些。數(shù)據(jù)結(jié)構(gòu)17弗羅伊德(Floyd)算法思想 設(shè)頂點集S(初值為空)，用數(shù)組A的每個元素Dij保存從vi 只經(jīng)過S中的頂點到達vj 的最短路徑長度，其思想是： 初始時令S= ， Dij的賦初值方式是： 將圖中一個頂點vk 加入到S中，修改Dij的

14、值，修改方法是： Dij= MinDij , (Dik+Dkj) 原因：從vi 只經(jīng)過S中的頂點(vk)到達vj 的路徑長度可能比原來不經(jīng)過vk的路徑更短。 重復，直到G的所有頂點都加入到S中為止。數(shù)據(jù)結(jié)構(gòu)18wij ij且E， wij為弧上的權(quán)值 ij且不屬于EDij =0 i=j時弗羅伊德(Floyd)算法數(shù)據(jù)結(jié)構(gòu)19v0v1v2643112cba 4 116 23 DD(-1) D(0) D(1) D(2) 0120120120120411411464616262625223373737PP(-1) P(0) P(1) P(2) 0120120120120abacabacababcababc1babcbabcbabcbcabc2cacacabcacabcacab圖的小結(jié) 數(shù)據(jù)結(jié)構(gòu)20圖的存儲結(jié)構(gòu)鄰接矩陣鄰接表邊數(shù)組十字鏈表鄰接多重表圖的遍歷深度優(yōu)先遍歷(DFS)廣度優(yōu)先遍歷(BFS)圖的小結(jié) 理解算法思想，根據(jù)具體問題選擇適當?shù)乃惴?數(shù)據(jù)結(jié)構(gòu)21圖的應(yīng)用最小生成樹有向無環(huán)圖應(yīng)用最短路徑AOV網(wǎng)AOE網(wǎng)Prim算法Kruskal算法Dijkstra算法Floyd算法隨堂練習1設(shè)一有向圖G=(V,E