1、第7章 圖 7.1 圖的定義和術(shù)語 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性問題 7.5 有向無環(huán)圖及其應(yīng)用 7.6 最短路徑,7.6 最短路徑,所謂最短路徑問題是指：如果從圖中某一頂點（稱為源點）出發(fā)到達另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權(quán)值總和達到最小。,A到E的路徑有： AE：100 ADE：90 ADCE：60 ABCE：70,1.單源點最短路徑 2.所有頂點對之間的最短路徑,問題描述：給定帶權(quán)有向圖G(V, E)和源點vV，求從v到G中其余各頂點的最短路徑。,單源點最短路徑問題,應(yīng)用實例計算機網(wǎng)絡(luò)傳輸?shù)膯栴}：怎樣找到一種最經(jīng)

2、濟的方式，從一臺計算機向網(wǎng)上所有其它計算機發(fā)送一條消息。,迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法Dijkstra算法。,基本思想：設(shè)置一個集合S 存放已經(jīng)找到最短路徑的頂點，S 的初始狀態(tài)只包含源點v，對vi V-S，假設(shè)從源點v到vi 的有向邊為最短路徑。以后每求得一條最短路徑v, , vk，就將vk 加入集合S中，并將路徑v, , vk , vi與原來的假設(shè)相比較，取路徑長度較小者為最短路徑。重復(fù)上述過程，直到集合V 中全部頂點加入到集合S 中。,Dijkstra算法,Dijkstra算法的基本思想,假設(shè) S為已求得最短路徑的終點的集合，則可證明：下

3、一條最短路徑(設(shè)其終點為x)或者是弧(v，x)，或者是中間只經(jīng)過S中的頂點而最后到達頂點x的路徑。這可用反證法來證明。假設(shè)此路徑上有一個頂點不在S中，則說明存在一條終點不在S而長度比此路徑短的路徑。但是，這是不可能的。因為我們是按路徑長度遞增的次序來產(chǎn)生各最短路徑的，即長度比此路徑短的所有路徑均己產(chǎn)生，它們的終點必定在S中，即假設(shè)不成立。,10,50,30,10,100,20,60,S=A AB:(A, B)10 AC:(A, C) AD: (A, D)30 AE: (A, E)100,10,50,30,10,100,20,60,S=A, B AB:(A, B)10 AC:(A, B, C)6

4、0 AD: (A, D)30 AE: (A, E)100,10,50,30,10,100,20,60,S=A, B AB:(A, B)10 AC:(A, B, C)60 AD: (A, D)30 AE: (A, E)100,10,50,30,10,100,20,60,S=A, B, D AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, E)90,10,50,30,10,100,20,60,S=A, B, D AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, E)90,10,50,30,10,

5、100,20,60,S=A, B, D, C AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, C, E)60,10,50,30,10,100,20,60,S=A, B, D, C, E AB:(A, B)10 AC:(A, D, C)50 AD: (A, D)30 AE: (A, D, C, E)60,例：給定帶權(quán)有向圖G和源點v, 求從v到G中其余各頂點的最短路徑。,V5,V0,V2,V4,V1,V3,100,300,10,60,10,20,50,5,V0,V2,V4,V3,V5,V0,始點 終點 Di 最短路徑,V1 V2 V3 V4

6、V5, 10 30 100, 10 30 100, 10 60 30 100, 10 60 30 100, 10 50 30 100,(V0, V2) (V0, V4) (V0, V5),(V0, V2) (V0, V4) (V0, V5),(V0, V2) (V0, V2, V3) (V0, V4) (V0, V5),(V0, V2) (V0, V2, V3) (V0, V4) (V0, V5),(V0, V2) (V0, V4, V3) (V0, V4) (V0, V5), 10 50 30 90,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V5), 1

7、0 50 30 90,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V5), 10 50 30 60,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V3, V5), 10 50 30 60,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V3, V5),輔助結(jié)構(gòu),int D Dv:表示當(dāng)前從源v0到頂點v的最短路徑長度 int P Pvw為TRUE，則w是從v0到v當(dāng)前求得最短路徑上的頂點 Pv:表示從源v0到頂點v的最短路徑上頂點v的所有前驅(qū)頂點 int final finalv為TRUE當(dāng)且

8、僅當(dāng)vS，即已經(jīng)求得v0到v的最短路徑,Dijkstra算法,(1) 假設(shè)我們以帶權(quán)的鄰接矩陣arcs表示有向網(wǎng)。 S：已求得最短路徑的終點的集合。初始為空。 D初始化 Dvi=arcsv0vi vi V (2) 選擇vj，使得Dj=MinDi|vi V-S 令S=Svj (3) 修改從v出發(fā)到集合V-S上任意頂點vk可達的最短路徑長度。 若 Dj+arcsjk Dk, 則Dk=Dj+arcsjk (4) 重復(fù)(2),(3)共n-1次。 由此求得從v到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。,V0 V1 V2 V3 V4 V5 V0 10 30 100 V1 5 V2 50 V3 10

9、 V4 20 60 V5 ,V0,V2,V4,V3,V5 ,V1,V0,V2,V4,V3,V5,V0,V2,V4,V3,V0,V2,V4,V0,V2,S=V0,V1,V5,V3,V4,V2,Vj,V5,V4,V3,V2,V1,i=5,i=4,i=3,i=2,i=1,D 終點,7.6 最短路徑,7.6.1 單源點最短路徑 7.6.2 所有頂點對之間的最短路徑,問題描述： 已知一個各邊權(quán)值均大于 0 的帶權(quán)有向圖，對每對頂點 vivj，要求求出每一對頂點之間的最短路徑和最短路徑長度。 解決方案： 1. 每次以一個頂點為源點，重復(fù)執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對頂點之間的最短路徑?？偟膱?zhí)

10、行時間為O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。時間復(fù)雜度也為O(n3)。,弗洛伊德算法思想 欲求Vi到Vj的最短路徑，依次求得中間頂點序號不大于k（k=0,1,.n-1）的最短路徑。 具體過程P190.,定義一個n階方陣序列 D(-1),D(0),D(1),D(2),D(k),D(n-1) 其中： D(-1)ij= arcsij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 0kn-1 可見，D(1)ij就是從vi到vj的中間頂點的序號不大于1的 最短路徑的長度; D(k)ij就是從vi到vj的中間頂點的序號不大于k的 最短路徑的長度;

11、D(n-1)ij就是從vi到vj的最短路徑的長度。,各頂點間的最短路徑及其路徑長度,最短路徑弗洛伊德舉例,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,P(2),P(1),P(0),P(-1),P,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,D(2),D(1),D(0),D(-1),D,本章小結(jié),1.熟悉圖的各種存儲結(jié)構(gòu)及構(gòu)造算法(特別是鄰接矩陣和鄰接表)，了解實際問題的求解效率與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系。 2.熟練掌握圖的兩種搜索路徑的遍歷及算法。 3.掌握以下內(nèi)容： 圖的最小生成樹和求最小生成樹算法的思想; AOV網(wǎng)絡(luò)的拓撲排序問題； AOE網(wǎng)絡(luò)的關(guān)鍵路