第五部分圖論第二部分教學(xué)ppt課件

1、第 五 章 圖 論 (第二部分)1. 通路通路2. 圖的連通性圖的連通性3. 賦權(quán)圖的最短通路賦權(quán)圖的最短通路賦權(quán)圖與邊的權(quán)賦權(quán)圖與邊的權(quán) 定義定義權(quán)權(quán) 在圖的點(diǎn)或者邊上標(biāo)明的信息在圖的點(diǎn)或者邊上標(biāo)明的信息(數(shù)量數(shù)量)稱為權(quán)。稱為權(quán)。邊邊e的權(quán)記為的權(quán)記為W(e)； 假設(shè)用兩個(gè)端點(diǎn)的序列假設(shè)用兩個(gè)端點(diǎn)的序列(u, v)表示邊，那么邊表示邊，那么邊(u,v)的權(quán)記為的權(quán)記為W(u,v) 。規(guī)定：規(guī)定： (1) W(uu) = 0， 假設(shè)假設(shè)(u, u) E(G), (2) W(uv) = , 假設(shè)假設(shè)(u, v) E(G)。 定義定義賦權(quán)圖賦權(quán)圖 頂點(diǎn)或邊含有權(quán)的圖稱為賦權(quán)圖。賦權(quán)圖可以是有向圖

2、或者無向圖。頂點(diǎn)或邊含有權(quán)的圖稱為賦權(quán)圖。賦權(quán)圖可以是有向圖或者無向圖。例例: 賦權(quán)圖邊權(quán)值例賦權(quán)圖邊權(quán)值例 W(a,b)=5，W(a,a)=0，W(b,d)=，W(a,d)=8 abcd5124820最短通路最短通路 定義定義 最短通路最短通路在一個(gè)邊賦權(quán)的圖在一個(gè)邊賦權(quán)的圖G G中，從中，從u u到到v v的一切通路中，邊的一切通路中，邊權(quán)值和最小的通路，稱為權(quán)值和最小的通路，稱為u u到到v v的最短通路最短的最短通路最短途徑，最短通路的邊權(quán)和稱為途徑，最短通路的邊權(quán)和稱為u u到到v v的間隔。的間隔。 兩點(diǎn)間的最短通路必為根本通路。兩點(diǎn)間的最短通路必為根本通路。 最短通路例最短通路例

3、515217420268AFBCDE枚舉法求最短通路枚舉法求最短通路 求求a到到c的最短通路的最短通路a到到c的根本通路有：的根本通路有：(a, b, c)邊權(quán)和為邊權(quán)和為5+4=9;(a, c)邊權(quán)和為邊權(quán)和為12;(a, d, c)邊權(quán)和為邊權(quán)和為8+20= 28。最短路為：最短路為： abc，因此，因此a到到c的間隔為的間隔為9abcd5124820狄克斯特洛狄克斯特洛(Dijkstra)算法算法l求圖求圖G=(V,E)中從結(jié)點(diǎn)中從結(jié)點(diǎn)a到結(jié)點(diǎn)到結(jié)點(diǎn)z的最短通路。的最短通路。l l根本思想動(dòng)態(tài)規(guī)劃法根本思想動(dòng)態(tài)規(guī)劃法l (1) 求出以求出以a為起點(diǎn)，為起點(diǎn)，V-a中的點(diǎn)為終點(diǎn)的最小最短通

4、路中的點(diǎn)為終點(diǎn)的最小最短通路P1；設(shè)；設(shè)P1終點(diǎn)為終點(diǎn)為t1;l 假設(shè)假設(shè)t1 = z，那么，那么P1為為a到到z的最短通路；的最短通路；l 否那么，執(zhí)行否那么，執(zhí)行(2)l(2) 求出以求出以a為起點(diǎn)，為起點(diǎn)， V-a,t1中的點(diǎn)為終點(diǎn)的最小最短通路中的點(diǎn)為終點(diǎn)的最小最短通路P2；設(shè)；設(shè)P2終點(diǎn)為終點(diǎn)為t2；l 假設(shè)假設(shè)t2 = z，那么，那么P2為為a到到z的最短通路；的最短通路；l 否那么，執(zhí)行否那么，執(zhí)行(3)l(3) 求出以求出以a為起點(diǎn)，為起點(diǎn)，V-a,t1,t2中的點(diǎn)為終點(diǎn)的最小最短通路中的點(diǎn)為終點(diǎn)的最小最短通路P3；設(shè)設(shè)P3終點(diǎn)為終點(diǎn)為t3；l 假設(shè)假設(shè)t3= z，那么，那么P

5、3為為a到到z的最短通路；的最短通路；l 否那么，執(zhí)行否那么，執(zhí)行(4)l(4) 依此類推，直到求得的第依此類推，直到求得的第k條最短通路條最短通路Pk；終點(diǎn)為；終點(diǎn)為z。狄克斯特洛算法：相關(guān)定義狄克斯特洛算法：相關(guān)定義設(shè)設(shè)G=(V, E)G=(V, E)，求，求G G中中a a到到z z的最短通路。的最短通路。 定義定義 目的集目的集目的集目的集T T是滿足以下條件的集合：是滿足以下條件的集合：(1) T (1) T V V(2) z (2) z T, z T, z是最短通路的終點(diǎn)是最短通路的終點(diǎn)(3) a (3) a T, a T, a是最短通路的起點(diǎn)是最短通路的起點(diǎn) 定義定義 目的目的

6、設(shè)設(shè)t1 t1 T T，由，由a a到到t1t1但不經(jīng)過目但不經(jīng)過目的集的集T T中其它頂點(diǎn)的一切通路中，各中其它頂點(diǎn)的一切通路中，各邊的權(quán)之和的最小者，稱為邊的權(quán)之和的最小者，稱為t1t1關(guān)于關(guān)于目的集目的集T T的目的，記作的目的，記作DT(t1).DT(t1).設(shè)設(shè)T=c, e, f, g, z, T=c, e, f, g, z, 求求DT(c).DT(c).a a到到c c但不經(jīng)過目的集但不經(jīng)過目的集T T中其它頂點(diǎn)的中其它頂點(diǎn)的一切根本通路一切根本通路: :(a, b, c): (a, b, c): 各邊權(quán)之和各邊權(quán)之和: 1+2 = 3: 1+2 = 3(a, c): (a, c)

7、: 各邊權(quán)之和各邊權(quán)之和: 4: 4(a, d, c): (a, d, c): 各邊權(quán)之和各邊權(quán)之和: 4+3 = 7: 4+3 = 7 DT(c) = 3badecfgz1442396357143TG狄克斯特洛算法：原理狄克斯特洛算法：原理原理原理: 設(shè)目的集設(shè)目的集T = t1, t2, , tn, 其中其中t1為為T中目的最小中目的最小的點(diǎn)，即：的點(diǎn)，即：DT(t1) = minDT(t1), DT(t2) , , DT(tn) (1) 始點(diǎn)始點(diǎn)a到到t1的最短通路的邊權(quán)和就是的最短通路的邊權(quán)和就是DT(t1) (2) 對恣意對恣意2 in， a到到t1的最短通路的最短通路 a到到ti的

8、最短通的最短通路路badecfgz1442396357143TG狄克斯特洛算法：原理證明狄克斯特洛算法：原理證明1 證明：證明： (1) (反證法反證法) 假設(shè)假設(shè)a到到t1的最短通路的權(quán)和不是的最短通路的權(quán)和不是DT(t1). 知知DT(t1)是從是從a到到t1但不經(jīng)過但不經(jīng)過T中其它頂點(diǎn)中其它頂點(diǎn)的通路中權(quán)和最小者，所以假設(shè)存在另一條權(quán)的通路中權(quán)和最小者，所以假設(shè)存在另一條權(quán)和小于和小于DT(t1)的新通路，那么該通路一定至少的新通路，那么該通路一定至少經(jīng)過經(jīng)過T中一個(gè)其它頂點(diǎn)。中一個(gè)其它頂點(diǎn)。狄克斯特洛算法：原理證明狄克斯特洛算法：原理證明2l證明證明(續(xù)續(xù))：l 設(shè)新通路的邊權(quán)和為設(shè)新

9、通路的邊權(quán)和為dnew，那么，那么l dnew DT(t1) l 其中其中w(t2t1) 表示新通路中表示新通路中t2到到t1的各邊權(quán)之和。的各邊權(quán)之和。l 這與這與“dnew DT(t1)矛盾。矛盾。l a到到t1的最短通路的權(quán)和只能是的最短通路的權(quán)和只能是DT(t1).aTt1t2狄克斯特洛算法：原理證明狄克斯特洛算法：原理證明2l證明證明(續(xù)續(xù))：l (2) (反證法反證法) 假設(shè)存在假設(shè)存在ti(i2) ，使得，使得a到到ti的最短通路小于的最短通路小于a到到t1的最短通路。的最短通路。設(shè)該通路為設(shè)該通路為P，邊權(quán)值和為，邊權(quán)值和為d。那么。那么dDT(t1)且且d DT(t1) l

10、其中其中w(t2t1) 表示表示P中中t2到到ti的各邊的各邊權(quán)之和。權(quán)之和。l 這與這與“d DT(t1)矛盾。矛盾。l (2)得證。得證。aTtit2狄克斯特洛算法狄克斯特洛算法l求圖求圖G=(V, E)G=(V, E)中中a a到到z z的最短通路。的最短通路。l 步驟：步驟：l 1 1令初始目的集令初始目的集T1T1V-aV-a。求。求T1T1中目的最小的結(jié)點(diǎn)，中目的最小的結(jié)點(diǎn)，設(shè)為設(shè)為t1t1。l 假設(shè)假設(shè)t1=zt1=z，那么，那么DT1(t1)DT1(t1)為為a a到到z z的最短通路邊權(quán)和。的最短通路邊權(quán)和。 l 否那么，執(zhí)行否那么，執(zhí)行2 2l 2 2令令T2=T1-t1,

11、T2=T1-t1,求求T2T2中目的最小的結(jié)點(diǎn)，設(shè)為中目的最小的結(jié)點(diǎn)，設(shè)為t2t2。l 假設(shè)假設(shè)t2=z,t2=z,那么那么DT2(t2)DT2(t2)為為a a到到z z最短通路邊權(quán)和。最短通路邊權(quán)和。l 否那么，執(zhí)行否那么，執(zhí)行(3)(3)l 3 3 依此類推，直到求得某個(gè)目的集依此類推，直到求得某個(gè)目的集TkTk，使得，使得z z為為TkTk中中目的最小的結(jié)目的最小的結(jié) l 點(diǎn)，那么點(diǎn)，那么DTk(z)DTk(z)為為a a到到z z的最短通路的邊權(quán)和。的最短通路的邊權(quán)和。l關(guān)鍵：求結(jié)點(diǎn)關(guān)于目的集關(guān)鍵：求結(jié)點(diǎn)關(guān)于目的集TiTi的目的。的目的。 知當(dāng)前目的集為知當(dāng)前目的集為Tm=tm, t

12、m+1, , tn，且，且DTm(ti)是是ti關(guān)于目的集關(guān)于目的集T的目的，的目的，tm是最小目的點(diǎn)。是最小目的點(diǎn)。 要求新的目的集要求新的目的集Tm+1= Tm tm中恣意點(diǎn)中恣意點(diǎn)ti的目的目的的 可用下公式求得：可用下公式求得： tmtntm+1tmTmTm+1tm-1t2t1a注：注：當(dāng)當(dāng)tmtm與與titi不鄰接時(shí)，不鄰接時(shí)，W(tm,ti)W(tm,ti)nmittWtDTtDTDTimmmimm,.,1),()(),(min(1狄克斯特洛算法：執(zhí)行步驟狄克斯特洛算法：執(zhí)行步驟求圖求圖G=(V, E)G=(V, E)中中a a到到z z的最短通路。的最短通路。 算法算法 執(zhí)行步驟

13、：執(zhí)行步驟：(1) (1) 將目的集設(shè)置為：將目的集設(shè)置為：T = V aT = V a(2) (2) 對恣意對恣意v vT T，令，令DT(v)=W(a,v)DT(v)=W(a,v)； (3) (3) 將將T T中目的值最小的點(diǎn)中目的值最小的點(diǎn)t t從從T T中剔除，即令中剔除，即令T TT Ttt； 。(4) (4) 假設(shè)假設(shè)t = zt = z，那么，那么DT(z)DT(z)為為a a到到z z的最短途徑權(quán)值，的最短途徑權(quán)值，算法終了。算法終了。 否那么即否那么即t zt z ，執(zhí)行以下操作：，執(zhí)行以下操作： 對一切對一切v v T T，令，令DT(v)=min(DT(v), DT(v)

14、=min(DT(v), DT(t)+W(t,v)DT(t)+W(t,v)； 反復(fù)反復(fù)(3).(3).算法執(zhí)行終了后，算法執(zhí)行終了后，DT(z)DT(z)就是從就是從a a到到z z的最短通路的權(quán)的最短通路的權(quán)和。和。狄克斯特洛算法求最短通路舉例狄克斯特洛算法求最短通路舉例首先，取初始目的集首先，取初始目的集T1b,c,d,e,f,g,z。易見易見: DT1(b) = 1 通路：通路：ab DT1(c) = 4 通路：通路：ac DT1(d) = 4 通路：通路：ad DT1(e) = DT1(f) = DT1(g) = DT1(z)= 無通路無通路T1比較各點(diǎn)的目的可比較各點(diǎn)的目的可知，知，b

15、 b是最小的目的是最小的目的點(diǎn)，點(diǎn)，b b的目的對應(yīng)的的目的對應(yīng)的通路為通路為abab。211(c)min(c),( )( , )min(4,12)3DTDTDT bW b c212T =T , , , , ,Tbc d e g z令中各點(diǎn)的指標(biāo)為211( )min( ),( )( , )min(4,)4DT dDT dDT bW b d 211( )min( ),( )( , )min( ,1 9)10DT eDT e DT bW b e211( )min( ),( )( ,)min( ,)DTfDT fDT bW b f 211( )min( ),( )( , )min( ,)DT gDT

16、 gDT bW b g 211( )min( ),( )( , )min( ,)DT zDT z DT bW b z c c是目的最小的點(diǎn)。是目的最小的點(diǎn)。T2通路：通路：abc通路：通路：ad通路：通路：abe通路：無通路：無通路：無通路：無通路：無通路：無a a到到c c的最短通路為：的最短通路為：abc,abc,邊權(quán)和為邊權(quán)和為DT2(c)=3DT2(c)=3 DT1(b) = 1 通路：通路：ab DT1(c) = 4 通路：通路：ac DT1(d) = 4 通路：通路：ad DT1(e) = DT1(f) = DT1(g) = DT1(z)= 無通路無通路322( )min( ),(

17、 )( , )min(4,33)4DT dDT dDT cW c d322( )min( ),( )( , )min(10,36)9DT eDT e DT cW c e322( )min( ),( )( ,)min( ,33)6DTfDTfDT cW c f322( )min( ),( )( , )min( ,35)8DT gDT gDT cW c g322( )min( ),( )( , )min( ,)DT zDT z DT cW c z 323T =T , , , ,Tcd e f g z令中各點(diǎn)的指標(biāo)為通路：通路：ad通路：通路：abce通路：通路：abcf通路：通路：abcg通路：無

18、通路：無比較T3中各點(diǎn)目的可知：d的目的最小，故DT3(d)=4是a到d的最短途徑長度，ad是a到d的最短途徑T3433( )min( ),( )( , )min(9,)9DT eDT e DT dW d e 433( )min( ),( )( ,)min(6,)6DTfDTfDT dW d f 433( )min( ),( )( , )min(8,47)8DT gDT gDT dW d g433( )min( ),( )( , )min( ,)DT zDT z DT dW d z 令 T4T3d=e, f, g, zT4中各結(jié)點(diǎn)的目的為： 通路：通路：abce通路：通路：abcf通路：通路：

19、abcg通路：無通路：無比較T4中各點(diǎn)目的可知：f的目的最小，故DT4(f)=6是a到f的最短途徑長度，abcf是a到f的最短途徑。T4544( )min( ),( )( , )min(9,62)8DT eDT e DTfW f e544( )min( ),( )( , )min(8,66)8DT gDT g DTfW f g544( )min( ),( )( , )min( ,6 4) 10DT zDT z DT fW f z比較T4中各點(diǎn)目的可知：e和g的目的一樣，且最小，故可選其中一個(gè)，DT5(e)=8是a到e的最短途徑長度，abcfe是a到e的最短途徑。令 T5T4f=e, g, z

20、T5中各結(jié)點(diǎn)的目的為： 通路：通路：abcfeT5通路：通路：abcg通路：通路：abcg655( )min( ),( )( , )min(8, )8DT gDT g DT eW e g 655( )min( ),( )( , )min(10,8 1)9DT zDT z DT eW e z令 T6T5e=g, z T6中各結(jié)點(diǎn)的目的為： T6比較T6中各點(diǎn)目的可知：f的目的最小，故DT6(g)=6是a到g的最短途徑長度，abcg是a到g的最短途徑。通路：通路：abcg通路：通路：abcfez令 T7T6g=z T7中各結(jié)點(diǎn)的目的為： 故a到z的最短通路邊權(quán)和為DT7(z)=9， 通路為abcf

21、ez通路：通路：abcfezT79) 38 , 9min(),()(),(min()(667zgWgDTzDTzDT求最短通路的表格表示法求最短通路的表格表示法步驟：步驟： (1) 先把先把T1=V a中各點(diǎn)寫在第一行上，把各點(diǎn)的中各點(diǎn)寫在第一行上，把各點(diǎn)的目的寫在第二行上目的寫在第二行上 然后圈出其中最小目的點(diǎn)。然后圈出其中最小目的點(diǎn)。b bc cd de ef fg gz z4 44 41T1b bc cd de ef fg gz z4 44 4211( )min( ),( )( , )DT tDT tDT bW b t (2) 在第三行上，相應(yīng)地寫上在第三行上，相應(yīng)地寫上T2=T1b中各點(diǎn)的指中各點(diǎn)的指 標(biāo)。在求標(biāo)。在求T2中點(diǎn)中點(diǎn)t的目的時(shí)，利用公式的目的時(shí)，利用公式 求出求出T2中各點(diǎn)的目的后，圈出最小目的點(diǎn)。中各點(diǎn)的目的后，圈出最小目的點(diǎn)。b bc cd de ef fg gz z4 44 44 410103T2T1T1在第四行上，相應(yīng)地寫上在第四行上，相應(yīng)地寫上T3=T2 c 中各點(diǎn)的目的。中各點(diǎn)的目的。利用公式：利用公式：322( )min( ),( )( , )DT tDT tDT cW c t求出求出T3的目的以后，圈出其中最小目的的點(diǎn)。的目的以后，圈出其中最小目的的點(diǎn)。b bc cd de ef fg gz z4 44 44 41