第12章 圖(二)

1、計算機與控制工程學院第第1212章章 圖（二）圖（二）計算機與控制工程學院主要內(nèi)容主要內(nèi)容 最短路徑最短路徑 拓撲排序拓撲排序 關(guān)鍵路徑關(guān)鍵路徑2計算機與控制工程學院最短路徑問題最短路徑問題 無權(quán)圖的最短路徑問題無權(quán)圖的最短路徑問題 比較簡單，即兩點之間邊數(shù)最少的路徑比較簡單，即兩點之間邊數(shù)最少的路徑 有向帶權(quán)圖有向帶權(quán)圖的最短路徑問題的最短路徑問題 可理解為兩地間交通費用最少問題可理解為兩地間交通費用最少問題 分為單源最短路徑、每對點最短路徑兩類分為單源最短路徑、每對點最短路徑兩類3計算機與控制工程學院單源最短路徑單源最短路徑 有向圖有向圖G G，每條邊都有非負權(quán)重（耗費），每條邊都有非負權(quán)

2、重（耗費） 路徑長度路徑長度路徑中邊的權(quán)重之和路徑中邊的權(quán)重之和 單源最短路徑：給定源頂點單源最短路徑：給定源頂點s s，求它到其他，求它到其他任意頂點（目的頂點）的最短路徑任意頂點（目的頂點）的最短路徑4計算機與控制工程學院單源最短路徑例單源最短路徑例5計算機與控制工程學院DijkstraDijkstra算法算法 S S：“已求出最短路徑頂點集合已求出最短路徑頂點集合”，初始為，初始為ss L=V - SL=V - S 每個步驟從每個步驟從L L選取一個頂點選取一個頂點v v加入加入S S 貪心準則：貪心準則：v v是是L L中距中距s s距離最短者距離最短者 新最短路徑新最短路徑= =已有

3、最短路徑已有最短路徑+ +一條邊一條邊每個頂點無需保存其完整路徑，保存路徑中它每個頂點無需保存其完整路徑，保存路徑中它的前一頂點即可的前一頂點即可6計算機與控制工程學院實現(xiàn)實現(xiàn) 數(shù)組數(shù)組p p：保存路徑（上例：保存路徑（上例：0, 1, 1, 3, 40, 1, 1, 3, 4） pipi：最短路徑中頂點：最短路徑中頂點i i的前驅(qū)頂點的前驅(qū)頂點 從終點開始，逆向即可獲取路徑從終點開始，逆向即可獲取路徑 數(shù)組數(shù)組d d：當前最短路徑長度：當前最短路徑長度 i i在在S S中，中，didi：s si i的真正最短路徑長度（最終結(jié)的真正最短路徑長度（最終結(jié)果）果） i i在在L L中，中，didi

4、：當前最短路徑長度：當前最短路徑長度s sj(j(S)S)i i的路徑長度（最短者）：的路徑長度（最短者）：dj+aji dj+aji 從從L L中選擇中選擇v v加入加入S S后，后，S S發(fā)生變化，發(fā)生變化，L L中的中的didi可能變可能變得更小，應進行更新得更小，應進行更新7計算機與控制工程學院運算實例：解題形式運算實例：解題形式1 1 1 2 3 4 5d=0, 4, 2, , 8p=0, 1, 1, 0, 1 1 2 3 4 5d=0, 4, 2, 3, 8 p=0, 1, 1, 3, 1 1 2 3 4 5d=0, 4, 2, 3, 6 p=0, 1, 1, 3, 4 1 2 3

5、 4 5d=0, 4, 2, 3, 6 p=0, 1, 1, 3, 4 1 2 3 4 5d=0, 4, 2, 3, 6 p=0, 1, 1, 3, 48S=1S=1, 3, 13S=1, 3, 4, 134S=1, 3, 4, 2, 12S=1, 3, 4, 2, 51345計算機與控制工程學院運算實例運算實例9計算機與控制工程學院10計算機與控制工程學院11計算機與控制工程學院12計算機與控制工程學院DijkstraDijkstra算法偽代碼算法偽代碼1)1) 初始化初始化d d i i=a a s si i （11i in n）對于鄰接于對于鄰接于s s的所有頂點的所有頂點i i，置，置

6、p p i i=s s，對于其余，對于其余的頂點置的頂點置p p i i=0=0對于對于p p i i 0 0的所有頂點建立的所有頂點建立L L表表2)2) 若若L L為空，終止，否則轉(zhuǎn)至為空，終止，否則轉(zhuǎn)至3)3)3)3) 從從L L中刪除中刪除d d值最小的頂點值最小的頂點4)4) 對于與對于與i i鄰接的所有還未到達的頂點鄰接的所有還未到達的頂點j j，更新，更新d d j j 值為值為minmin d d j j, , d d i i+a a i ij j若若d d j j 發(fā)生了變化且發(fā)生了變化且j j還未在還未在L L中，則置中，則置p p j j=i=i，并將并將j j加入加入L

7、 L，轉(zhuǎn)至，轉(zhuǎn)至2 213計算機與控制工程學院無序鏈表實現(xiàn)無序鏈表實現(xiàn)templatevoid AdjacencyWDigraph:ShortestPaths(int s, T d, int p)/ Shortest paths from vertex s, return shortest / distances in d and predecessor info in p. if (s n) throw OutOfBounds(); Chain L; / list of reachable vertices for / which paths have yet to be found Cha

8、inIterator I; 14計算機與控制工程學院無序鏈表實現(xiàn)（續(xù)）無序鏈表實現(xiàn)（續(xù)） / initialize d, p, and L for (int i = 1; i = n; i+) di = asi; if (di = NoEdge) pi = 0; else pi = s; L.Insert(0,i); 15計算機與控制工程學院無序鏈表實現(xiàn)（續(xù)）無序鏈表實現(xiàn)（續(xù)） / update d and p while (!L.IsEmpty() / more paths exist / find vertex *v in L with least d int *v = I.Initial

9、ize(L); int *w = I.Next(); while (w) if (d*w d*v) v = w; w = I.Next();16計算機與控制工程學院無序鏈表實現(xiàn)（續(xù)）無序鏈表實現(xiàn)（續(xù)）int i = *v; L.Delete(*v); for (int j = 1; j di + aij) dj = di + aij; if (!pj) L.Insert(0,j); pj = i; 17計算機與控制工程學院每一對點的最短路徑每一對點的最短路徑 所有點對間的最短路徑，所有點對間的最短路徑，all-pairs shortest-all-pairs shortest-paths pr

10、oblempaths problem，n(n-1)n(n-1)條條 簡單算法：每個頂點執(zhí)行單源最短路徑算法簡單算法：每個頂點執(zhí)行單源最短路徑算法18計算機與控制工程學院FloydFloyd算法算法 頂點編號為頂點編號為1 1n n c(i,j,k)c(i,j,k)：i ij j的的“最短路徑最短路徑”長度長度加了加了限制條件，路徑中頂點的最大編號為限制條件，路徑中頂點的最大編號為k k 存在邊存在邊c(i, j, 0)=c(i, j, 0)=的長度的長度 不存在邊不存在邊c(i, j, 0)=+c(i, j, 0)=+ c(i, i, 0)=0c(i, i, 0)=0 c(i, j, n)c(

11、i, j, n)最短路徑長度最短路徑長度19計算機與控制工程學院FloydFloyd算法算法 例例15.615.6：考慮上圖：考慮上圖 k=0, 1, 2, 3k=0, 1, 2, 3，c(1, 3, k)= +c(1, 3, k)= + ；c(1, 3, 4)=28c(1, 3, 4)=28 k=5, 6, 7k=5, 6, 7，c(1, 3, k)=10c(1, 3, k)=10； k=8, 9, 10k=8, 9, 10，c(1, 3, k)=9c(1, 3, k)=9最短路徑最短路徑20計算機與控制工程學院如何計算如何計算c(i, j, k)c(i, j, k) 頂點最大編號不超過頂點

12、最大編號不超過k k，兩種情況，兩種情況 路徑不包含路徑不包含k k，c(i, j, k)=c(i, j, k-1)c(i, j, k)=c(i, j, k-1) 包含包含k k，c(i, j, k)=c(i, k, k-1) + c(k, j, c(i, j, k)=c(i, k, k-1) + c(k, j, k-1)k-1) c(i,j,k)=minc(i,j,k-1), c(i,j,k)=minc(i,j,k-1), c(i,k,k-c(i,k,k-1)+c(k,j,k-1)1)+c(k,j,k-1) 遞歸算法，遞歸算法，Q Q(n2(n2n n) ) 迭代計算迭代計算Q Q(n(n3

13、 3) )21計算機與控制工程學院迭代計算偽代碼迭代計算偽代碼/ / /尋找最短路徑的長度尋找最短路徑的長度/ / /初始化初始化c c（i i，j j，1 1）for (int i=1for (int i=1； i = n ; i +)i = n ; i +)for (int for (int j j=1; =1; j j=n; =n; j j+)+) c( i , c( i ,j j, 0) = a (i , 0) = a (i ,j j); / a ); / a 是長度鄰接矩陣是長度鄰接矩陣/ / /計算計算c ( i ,c ( i ,j j, k ) ( 0 k = n ), k )

14、( 0 k = n )for(int k=1;k=n;k+)for(int k=1;k=n;k+)for (int i=1;i=n;i+)for (int i=1;i=n;i+) for (int for (int j j= 1 ;= 1 ;j j = n ; = n ;j j+ + )+ + )if (c(i,k,k-1)+c(k, if (c(i,k,k-1)+c(k, j j, k - 1) c (i, , k - 1) c (i, j j, k - 1), k - 1) c(i, c(i, j j, k) = c(i, k, k - 1) + c(k, , k) = c(i, k, k

15、 - 1) + c(k, j j, k - 1) ;, k - 1) ;else c(i, else c(i, j j, k) = c (i, , k) = c (i, j j, k - 1);, k - 1);22計算機與控制工程學院FloydFloyd算法例算法例ABCDA013 B01C502D40C023計算機與控制工程學院FloydFloyd算法例（續(xù)）算法例（續(xù)）12341013 2013502440C0c(i,j,1)=min(c(i,j,0), c(i,1,0)+c(1,j,0)12341013 20135602440C124計算機與控制工程學院FloydFloyd算法例（續(xù)）

16、算法例（續(xù)）12341013 20135602440C1c(i,j,2)=min(c(i,j,1), c(i,2,1)+c(2,j,1)123410123 201356024450C225計算機與控制工程學院FloydFloyd算法例（續(xù)）算法例（續(xù)）123410123 201356024450C2c(i,j,3)=min(c(i,j,2), c(i,3,2)+c(3,j,2)123410123 2601335602410450C326計算機與控制工程學院FloydFloyd算法例（續(xù)）算法例（續(xù)）123410123 2601335602410450C3c(i,j,4)=min(c(i,j,3

17、), c(i,4,3)+c(4,j,3)123410123 2601335602410450C427計算機與控制工程學院最終代碼最終代碼templatevoid AdjacencyWDigraph:AllPairs(T *c, int *kay)/ All pairs shortest paths. / Compute cij and kayij for all i and j. / initialize cij = c(i,j,0) for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) cij = aij; kayij = 0; for

18、(i = 1; i = n; i+) cii = 0;28計算機與控制工程學院最終代碼（續(xù)）最終代碼（續(xù)）/ compute cij = c(i,j,k) for (int k = 1; k = n; k+) for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) T t1 = cik; T t2 = ckj; T t3 = cij; if (t1 != NoEdge & t2 != NoEdge & (t3 = NoEdge | t1 + t2 t3) cij = t1 + t2; kayij = k; 29計算機與控制工程

19、學院最終代碼（續(xù)）最終代碼（續(xù)）void outputPath(int *kay, int i, int j)/ Actual code to output i to j path. if (i = j) return; if (kayij = 0) cout j ; else outputPath(kay, i, kayij); outputPath(kay, kayij, j);30計算機與控制工程學院最終代碼（續(xù)）最終代碼（續(xù)）templatevoid OutputPath(T *c, int *kay, T NoEdge, int i, int j)/ Output shortest

20、path from i to j. if (cij = NoEdge) cout There is no path from i to j endl; return; cout The path is endl; cout i ; outputPath(kay,i,j); cout endl;31計算機與控制工程學院主要內(nèi)容主要內(nèi)容 最短路徑最短路徑 拓撲排序拓撲排序 關(guān)鍵路徑關(guān)鍵路徑32計算機與控制工程學院工程和有向無環(huán)圖工程和有向無環(huán)圖 有向無環(huán)圖是描述復雜工程的有效工具有向無環(huán)圖是描述復雜工程的有效工具 工程可以分解為多個活動（工程可以分解為多個活動（ActivityActivity）

21、活動之間具有前后約束關(guān)系活動之間具有前后約束關(guān)系 工程問題轉(zhuǎn)化為工程問題轉(zhuǎn)化為 工程能否順利進行？工程能否順利進行？ 完成工程的最短時間是多少？完成工程的最短時間是多少？33計算機與控制工程學院拓撲排序拓撲排序 偏序：集合中僅有部分成員之間可比較偏序：集合中僅有部分成員之間可比較 全序：集合中全體成員之間均可比較全序：集合中全體成員之間均可比較 拓撲排序拓撲排序（Topological SortTopological Sort）：由某個集合上）：由某個集合上的一個偏序得到該集合上的一個全序的一個偏序得到該集合上的一個全序V1V2V3V4V1V2V3V434計算機與控制工程學院AOVAOV圖圖

22、用頂點表示活動，用箭頭表示活動間優(yōu)先關(guān)系的用頂點表示活動，用箭頭表示活動間優(yōu)先關(guān)系的有向圖稱為頂點活動網(wǎng)絡(luò)（有向圖稱為頂點活動網(wǎng)絡(luò)（Activity On VertexActivity On Vertex，AOVAOV） 頂點頂點i i在頂點在頂點j j之前，意味著活動之前，意味著活動i i是活動是活動j j的先決條件的先決條件 顯然不應該出現(xiàn)有向環(huán)，否則顯然不應該出現(xiàn)有向環(huán)，否則“活動活動k k是它自己的先決是它自己的先決條件條件”，不成立，不成立35計算機與控制工程學院AOVAOV網(wǎng)絡(luò)示例網(wǎng)絡(luò)示例36計算機與控制工程學院拓撲序列例拓撲序列例 123456123456/p>

23、6、215346215346 142356142356不是！不是！37計算機與控制工程學院利用貪心算法進行拓撲排序利用貪心算法進行拓撲排序 在有向圖中選一個沒有前驅(qū)的頂點且輸出在有向圖中選一個沒有前驅(qū)的頂點且輸出 從圖中刪除該頂點和所有從其發(fā)出的箭頭從圖中刪除該頂點和所有從其發(fā)出的箭頭 重復上述兩步，直至所有頂點均已輸出，或者當重復上述兩步，直至所有頂點均已輸出，或者當前圖中不存在無前驅(qū)的頂點為止前圖中不存在無前驅(qū)的頂點為止38計算機與控制工程學院算法描述算法描述設(shè)設(shè)n n是有向圖中的頂點數(shù)是有向圖中的頂點數(shù)設(shè)設(shè)V V是一個空序列是一個空序列while while ( (truetrue)設(shè)設(shè)

24、w w不存在入邊（不存在入邊（v v, ,w w），其中頂點），其中頂點v v不在不在V V中中如果沒有這樣的如果沒有這樣的w w，breakbreak把把w w添加到添加到V V的尾部的尾部 ifif( (V V中的頂點數(shù)少于中的頂點數(shù)少于n n) )算法失敗算法失敗elseelseV V是一個拓撲序列是一個拓撲序列39計算機與控制工程學院算法示例算法示例40V1V2V3V4V6V5V1V2V3V4V5V2V3V4V5V2V3V5Step1 Step2 Step3 Step4計算機與控制工程學院算法細化算法細化數(shù)據(jù)結(jié)構(gòu)的選擇數(shù)據(jù)結(jié)構(gòu)的選擇 拓撲序列拓撲序列V V如何描述？如何描述？如何找出候

25、選頂點？如何找出候選頂點？ VV一維數(shù)組一維數(shù)組v v棧棧保存候選頂點保存候選頂點 InDegreeInDegree保存頂點當前入度保存頂點當前入度41計算機與控制工程學院算法實現(xiàn)算法實現(xiàn) 初始初始 V V為空為空 InDegreeInDegree保存圖中頂點入度保存圖中頂點入度 將入度為將入度為0 0的頂點壓棧的頂點壓棧 每個步驟每個步驟 彈出棧頂頂點彈出棧頂頂點p p，加入，加入V V 并將并將p p的每個鄰接頂點的的每個鄰接頂點的InDegreeInDegree值減值減1 1 若某個頂點的若某個頂點的InDegreeInDegree值變?yōu)橹底優(yōu)? 0，將其壓棧，將其壓棧42計算機與控制工

26、程學院實現(xiàn)實現(xiàn)bool Network:Topological(int v) int n = Vertices(); / Compute in-degrees int *InDegree = new int n+1; InitializePos(); / graph iterator array for (int i = 1; i = n; i+) / initialize InDegreei = 0;43計算機與控制工程學院實現(xiàn)（續(xù)）實現(xiàn)（續(xù)） for (i = 1; i = n; i+) / 遍歷所有頂點的出邊，計算入度遍歷所有頂點的出邊，計算入度 int u = Begin(i); wh

27、ile (u) InDegreeu+; u = NextVertex(i); / Stack vertices with zero in-degree LinkedStack S; for (i = 1; i = n; i+) if (!InDegreei) S.Add(i);44計算機與控制工程學院實現(xiàn)（續(xù)）實現(xiàn)（續(xù)） / Generate topological order i = 0; / cursor for array v while (!S.IsEmpty() / select from stack int w; / next vertex S.Delete(w); vi+ = w

28、; int u = Begin(w); while (u) / update in-degrees InDegreeu-; if (!InDegreeu) S.Add(u); u = NextVertex(w); DeactivatePos(); delete InDegree; return (i = n);時間復雜度是時間復雜度是O(n+e)45計算機與控制工程學院拓撲排序要點拓撲排序要點 入度為入度為0 0的頂點即沒有前驅(qū)活動的，或前驅(qū)的頂點即沒有前驅(qū)活動的，或前驅(qū)活動都已經(jīng)完成的頂點，工程可以從這個頂活動都已經(jīng)完成的頂點，工程可以從這個頂點所代表的活動開始或繼續(xù)點所代表的活動開始或繼續(xù)

29、 算法每輸出一個頂點之后，要刪去從這個頂算法每輸出一個頂點之后，要刪去從這個頂點發(fā)出的邊，這意味著這個頂點所代表的活點發(fā)出的邊，這意味著這個頂點所代表的活動已經(jīng)完成，對于后續(xù)頂點所代表的活動來動已經(jīng)完成，對于后續(xù)頂點所代表的活動來說，該前驅(qū)活動已經(jīng)完成說，該前驅(qū)活動已經(jīng)完成46計算機與控制工程學院拓撲排序要點拓撲排序要點 如果一個節(jié)點有多個直接后繼，則拓撲排序如果一個節(jié)點有多個直接后繼，則拓撲排序的結(jié)果通常不唯一的結(jié)果通常不唯一 由于由于AOVAOV網(wǎng)絡(luò)中各頂點的地位是平等的，每網(wǎng)絡(luò)中各頂點的地位是平等的，每個頂點的編號是人為的，因此可以按照拓撲個頂點的編號是人為的，因此可以按照拓撲排序的結(jié)果

30、重新安排頂點的序號，生成排序的結(jié)果重新安排頂點的序號，生成AOVAOV網(wǎng)絡(luò)的新的鄰接矩陣存儲表示。其中，對角網(wǎng)絡(luò)的新的鄰接矩陣存儲表示。其中，對角線以下可以全為零。線以下可以全為零。47計算機與控制工程學院小練習小練習 寫出下圖的所有拓撲排序結(jié)果寫出下圖的所有拓撲排序結(jié)果 提示：共有提示：共有7 7種種48V1V2V6V5V3V4計算機與控制工程學院主要內(nèi)容主要內(nèi)容 最短路徑最短路徑 拓撲排序拓撲排序 關(guān)鍵路徑關(guān)鍵路徑49計算機與控制工程學院AOEAOE網(wǎng)網(wǎng) 一個帶權(quán)的有向無環(huán)圖，其中頂點表示事件一個帶權(quán)的有向無環(huán)圖，其中頂點表示事件，邊表示活動，權(quán)表示活動持續(xù)的時間，則，邊表示活動，權(quán)表示活

31、動持續(xù)的時間，則該圖稱為該圖稱為AOEAOE（Activity On EdgeActivity On Edge）網(wǎng)）網(wǎng)左圖所示工程：9個事件（里程碑）11項活動（必須完成的工作）V5含義是：a4和a5已完成a7和a8可開始50計算機與控制工程學院關(guān)鍵路徑關(guān)鍵路徑 將將AOEAOE網(wǎng)看作一個工程網(wǎng)看作一個工程 只有一個入度為只有一個入度為0 0的點（源點），一個出度為的點（源點），一個出度為0 0的的點（匯點）點（匯點） 完成整個工程需要多少時間？哪些活動是影響工完成整個工程需要多少時間？哪些活動是影響工程進度的關(guān)鍵？程進度的關(guān)鍵？ 關(guān)鍵路徑關(guān)鍵路徑（Critical PathCritical

32、Path） 從源點到匯點長度（時間和）最長的路徑從源點到匯點長度（時間和）最長的路徑 長度長度完成工程的最短時間完成工程的最短時間 上例：上例：(v(v1 1, v, v2 2, v, v5 5, v, v8 8, v, v9 9) )51計算機與控制工程學院關(guān)鍵活動關(guān)鍵活動 源點源點v v1 1v vi i的最長路徑長度：的最長路徑長度：事件事件v vi i的最早發(fā)生時間，的最早發(fā)生時間，v vi i發(fā)出的所有邊（活動）的最早開始時間發(fā)出的所有邊（活動）的最早開始時間 e(i)e(i)：活動：活動a ai i的最早開始時間的最早開始時間 最遲開始時間：最遲開始時間：l(i)l(i)，前提：不

33、影響工程進，前提：不影響工程進度度 l(i)=e(i)l(i)=e(i)：關(guān)鍵活動：關(guān)鍵活動 關(guān)鍵路徑上的活動都是關(guān)鍵活動關(guān)鍵路徑上的活動都是關(guān)鍵活動 通過計算通過計算l(i)l(i)、e(i)e(i)尋找關(guān)鍵活動尋找關(guān)鍵活動52計算機與控制工程學院l(i)l(i)和和e(i)e(i)的計算的計算 事件的最早發(fā)生時間事件的最早發(fā)生時間ve(j)ve(j)最遲發(fā)生時間最遲發(fā)生時間vl(j)vl(j) 活動活動a ai i由邊由邊表示表示dut()dut()表示其持續(xù)時間，則有表示其持續(xù)時間，則有 e(i)=ve(j) e(i)=ve(j) 含義是：活動含義是：活動i i要想開始至少需要等待的時間要想開始至少需要等待的時間 l(i)=vl(k)-dut()l(i)=vl(k)-dut() 含義是：活動含義是：活動i i開始之前最多空閑的時間開始之前最多空閑的時間jkaidut53計算機與控制工程學院ve(i)ve(i)的計算的計算 由由ve(0)=0ve(0)=0向前遞推向前遞推ve(j)=ve