d圖論例子(存檔)(北郵信通院陳鑫林教授授課PPT)

1、1 若干補(bǔ)充若干補(bǔ)充1.1.Ford(1956)-Moore(1957)-Bellman(1958)Ford(1956)-Moore(1957)-Bellman(1958) 算法算法由于由于DijkstraDijkstra算法只適用于弧長(zhǎng)為正的情形算法只適用于弧長(zhǎng)為正的情形, ,而而Ford(1956)-Moore(1957)-Bellman(1958)Ford(1956)-Moore(1957)-Bellman(1958)算法適算法適用于弧長(zhǎng)可為負(fù)用于弧長(zhǎng)可為負(fù), ,但不含負(fù)的有向回路的情形但不含負(fù)的有向回路的情形, ,并且并且在許多通信的論文中得到廣泛應(yīng)用在許多通信的論文中得到廣泛應(yīng)用,

2、,所以特做介紹所以特做介紹. .2Ford(1956)-Moore(1957)-Bellman(1958)Ford(1956)-Moore(1957)-Bellman(1958)算法算法它適用于弧長(zhǎng)可為負(fù)它適用于弧長(zhǎng)可為負(fù), ,但不含負(fù)的有向回路的情形但不含負(fù)的有向回路的情形. .算法思路算法思路: :從從s s到到j(luò) j至多至多k+1k+1條弧的最短有向路徑可以條弧的最短有向路徑可以由從由從s s到到j(luò) j至多含至多含k k條弧的最短路徑得到條弧的最短路徑得到. .因此因此, ,在第在第k k次迭代結(jié)束時(shí)次迭代結(jié)束時(shí), ,節(jié)點(diǎn)的標(biāo)記就表示從節(jié)點(diǎn)的標(biāo)記就表示從s s出發(fā)的含不多出發(fā)的含不多于于

3、k+1k+1條弧的最短路徑的長(zhǎng)度條弧的最短路徑的長(zhǎng)度. .設(shè)設(shè) 是給定的有是給定的有n n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)G(V,E,l)G(V,E,l)中從中從s s到到j(luò) j的不多于的不多于k k條弧的最短有向路徑的長(zhǎng)度條弧的最短有向路徑的長(zhǎng)度, ,首先設(shè)首先設(shè))(kjl1, 2 , 1),(, 0)1()(njjslllljkss1, 2 , 1,),(min,min,),()()()1(njsjijillllEjikikjkj對(duì)所有對(duì)所有3顯然顯然, ,從從s s到到j(luò) j至多含至多含k+1k+1條弧的最短有向路徑條弧的最短有向路徑可能由可能由k+1k+1條弧或較少的弧構(gòu)成條弧或較少的弧構(gòu)成,

4、 ,若它正好含若它正好含k+1k+1條條弧弧, ,則設(shè)則設(shè)(i,j)(i,j)是是 中的最后一條弧中的最后一條弧, ,那么那么 可以可以看成是由從看成是由從s s到到i i的含的含k k條弧的最短路徑條弧的最短路徑 和后續(xù)弧和后續(xù)弧(i,j)(i,j)構(gòu)成構(gòu)成, ,因此得因此得 的長(zhǎng)度是的長(zhǎng)度是如果如果 含含k k條或較少的弧條或較少的弧, ,則則 . .因此對(duì)因此對(duì)kn, kn, 時(shí)時(shí), ,算法終止算法終止. .如果在如果在k=n-1k=n-1時(shí)時(shí)對(duì)某個(gè)對(duì)某個(gè)j j有有 , ,那么網(wǎng)中必有負(fù)向回路那么網(wǎng)中必有負(fù)向回路, ,算法失算法失效效, ,并在第并在第n-1n-1次迭代時(shí)終止次迭代時(shí)終止

5、. .表明有負(fù)向回路表明有負(fù)向回路. .算法的計(jì)算復(fù)雜度為算法的計(jì)算復(fù)雜度為)1(,kjsP)1(,kjsP)1(,kjsP)1(,kjsP),(min)()()1(,)1(jillPllkikjskj)1(,kjsP)()1(kjkjll)()1(kjkjll)(3nO)()1(kjkjll)(,kisP4例例6664444811223555S570Sl4,44,4)1(1)2(1)3(1)4(1llll)1(4)2(4)3(4)4(4,95,5llll6,66,6)1(2)2(2)3(2)4(2llll)1(5)2(5)3(5)4(5,00,0llll40)3(6)4(6ll133)3(3

6、)4(3ll)1(3)2(313ll)1(6)2(6ll5,)6,5(),6,4(,min)2,00,min)5 ,3(),5 ,2(,min)1,99 ,min)4,5(),4, 1(,min)2,13876min,min)3 ,4(),3 ,2(min,min)2,( ,6min,4)2, 16min(,4min)1 ,3(),1 ,2(min,min)1(6,5 ,4,3,6,4:)1(5)1(4)1(6)2(6)1(3)1(2)1(5)2(5)1(5)1(1)1(4)2(4)1(4)1(2)1(3)2(3)1(2)1(2)2(2)1(3)1(2)1(1)2(1)1()1(2)1(1ll

7、llllllllllllllllllllllslllllllllkillli（經(jīng)經(jīng)（經(jīng)經(jīng)（經(jīng)經(jīng)，的的徑徑無(wú)無(wú)其其它它到到外外除除第第一一次次迭迭代代初初始始6)5( ,440,59min,min)6,5(),6,4(,min,0413,66min,0min)5,3(),5,2(,min)5( ,550,54min,9min)4,5(),4, 1(,min,1389,76min,13min)3,4(),3,2(min,min,6min4)213, 16min(,4min)1 ,3(),1 ,2(min,min)2()2(5)2(4)2(6)3(6)2(3)2(2)2(5)3(5)2(5)2(1)

8、2(4)3(4)2(4)2(2)2(3)3(3)2(2)2(2)3(2)2(3)2(2)2(1)3(1經(jīng)經(jīng)再再經(jīng)經(jīng)第第二二次次迭迭代代lllllllllllllllllllllllllllllllllk7)4( ,040,55min,4min)6,5(),6,4(,min,0413,66min,0min)5,3(),5,2(,min,550,54min,5min)4,5(),4, 1(,min)4( ,385,76min,13min)3,4(),3,2(min,min,6min,4)1 ,3(),1 ,2(min,min)3()3(5)3(4)3(6)4(6)3(3)3(2)3(5)4(5)3

9、(5)3(1)3(4)4(4)3(4)3(2)3(3)4(3)3(2)3(2)4(2)3(3)3(2)3(1)4(1再再經(jīng)經(jīng)再再經(jīng)經(jīng)第第三三次次迭迭代代lllllllllllllllllllllllllllllllllk8,),(min,min)4()4()4()4()5(jiijjljillllk第第四四次次迭迭代代算法在k=4n=7次迭代終止.0)(),6 ,4(),4, 5(),5 ,2(),2,()6 ,4( ,:6, 3)(),3 ,4(),4, 5(),5 ,2(),2,()3 ,4( ,:3, 5)(),4, 5(),5 ,2(),2,()4, 5( ,:4,0)(),5 ,2(

10、),2,(:5,6)(),2,(:2,4)(),1 ,(:1)4(6,)3(4,)4(6,)4(3,)3(4,)4(3,)3(4,)2(5,)3(4,)2(5,)2(5,)1(2,)1(2,)1(1 ,)1(1 ,sssssssssssssssPlsPPsPlsPPsPlsPPsPlsPsPlsPsPlsPs92.Floyd2.Floyd算法在以下情況可以簡(jiǎn)化算法在以下情況可以簡(jiǎn)化: :(1)(1)如有度數(shù)為如有度數(shù)為1 1的端的端, ,可把它們?nèi)サ粼僮鲇?jì)算可把它們?nèi)サ粼僮鲇?jì)算; ;設(shè)設(shè) 為度數(shù)為為度數(shù)為1 1的端的端, ,它只與它只與 相連相連, ,則則 與其它與其它端的最短徑必經(jīng)端的最短徑

11、必經(jīng) , ,所以所以(2)(2)如有度數(shù)為如有度數(shù)為2 2的端的端, ,則按下述方法去掉則按下述方法去掉: :設(shè)設(shè) 為度數(shù)為為度數(shù)為2 2的端的端, ,它只與它只與 相連相連, ,若若 , ,則可簡(jiǎn)單地去掉則可簡(jiǎn)單地去掉若若 , ,也可去掉也可去掉 , ,但把但把 改成改成 svivsviv)(表表最最短短距距離離wwdwijsisjsvjivv 和和ijsisjdddsvijsisjdddsvijd;sisjdd10不論那種情況不論那種情況, ,與其它端間的最短徑長(zhǎng)用下述公式與其它端間的最短徑長(zhǎng)用下述公式計(jì)算計(jì)算: :(3)(3)稀疏網(wǎng)的情況下可把全圖分成幾個(gè)部分來(lái)計(jì)算稀疏網(wǎng)的情況下可把全圖

12、分成幾個(gè)部分來(lái)計(jì)算, ,然后合并然后合并. .當(dāng)網(wǎng)的邊數(shù)遠(yuǎn)少于全聯(lián)網(wǎng)的邊數(shù)時(shí)當(dāng)網(wǎng)的邊數(shù)遠(yuǎn)少于全聯(lián)網(wǎng)的邊數(shù)時(shí), ,稱(chēng)稱(chēng)稀疏網(wǎng)稀疏網(wǎng). .此時(shí)往往存在割端或端數(shù)較少的割端此時(shí)往往存在割端或端數(shù)較少的割端. .對(duì)于有割端對(duì)于有割端 的網(wǎng)的網(wǎng)G,G,去掉后就把去掉后就把G G分成幾部分分成幾部分( (例例如三部分如三部分G1,G2,G3),G1,G2,G3),用用FloydFloyd算法分別求出算法分別求出的最短距離陣的最短距離陣 及路由陣及路由陣. .若若則則 間最短距離為間最短距離為,jksjiksiskwdwdMinwsv,321sssvGvGvG ,WWW221,GvGvijivv , jsi

13、sijwww111v22v3v4v5v6v7v8v1213345689019105350293208046840212036130)0(D例例1201641612141310531511131265021410121143201281091615141204651211108402114131210620313121195130)1(D0077777700005555700055557000303375530033755000007553300075533000)1(R,13875313153175187118vvvvvvvvvvvvvvvvw131v22v3v4v5v6v7v8v121334

14、5689. 4 , 3 , 2 , 1, 80033000030003000,0465402162035130353535) 1 () 1 (idwwdRDii14030333003300000330003300001281091204658402110620395130) 1 () 1 (RD151v22v3v4v5v6v7v8v1213345689. 8 , 7 , 6 , 5; 4 , 3 , 2 , 1, 80077000070007000,0164105365024320535335) 1 () 1 (ijjijiijwwjiddwwdRD16(3)(3)次短徑和可用徑次短徑和可用徑

15、: :若兩端間有幾條徑若兩端間有幾條徑, ,其中其中P1P1為最短徑為最短徑, ,而而P2P2與與P1P1無(wú)無(wú)公共邊卻有公共端公共邊卻有公共端, ,則稱(chēng)則稱(chēng)P2P2不共邊徑或邊分離徑不共邊徑或邊分離徑; ;若若P3P3與與P1P1除起終點(diǎn)外無(wú)公共端除起終點(diǎn)外無(wú)公共端( (必?zé)o公共邊必?zé)o公共邊),),則稱(chēng)則稱(chēng)P3P3為不共端徑或端分離徑為不共端徑或端分離徑. .求次短徑的方法求次短徑的方法1)1)對(duì)不共邊徑對(duì)不共邊徑從圖中去掉最短徑的所有邊從圖中去掉最短徑的所有邊, ,然后在剩下的圖中求然后在剩下的圖中求最短徑最短徑; ;2)2)對(duì)不共端徑對(duì)不共端徑從圖中去掉最短徑的所有中間端從圖中去掉最短徑的

16、所有中間端( (當(dāng)然段的關(guān)聯(lián)邊當(dāng)然段的關(guān)聯(lián)邊也去掉也去掉),),然后在剩下的圖中求最短徑然后在剩下的圖中求最短徑; ;17這個(gè)過(guò)程還可繼續(xù)下去.例:1v2v3v4v5v6vsvtv11111222335618從從 到到 有三條徑有三條徑: :svtv)(:)(:)(:6534232211端分離徑端分離徑邊分離徑邊分離徑最短徑最短徑tststsvvvvPvvvvvPvvvvP191v2v3v4v5v6vsvtv111223356邊分離的次短徑203v4v5v6vsvtv112235端分離的次短徑21可用徑可用徑在某些應(yīng)用中在某些應(yīng)用中,要求找一批滿(mǎn)足條件的徑要求找一批滿(mǎn)足條件的徑.當(dāng)有幾個(gè)當(dāng)有幾

17、個(gè)條件時(shí)條件時(shí),可先用一個(gè)條件求可用徑可先用一個(gè)條件求可用徑,再在其中篩選出再在其中篩選出滿(mǎn)足其它條件的可用徑滿(mǎn)足其它條件的可用徑.今用限制條件為徑長(zhǎng)的例子來(lái)說(shuō)明算法今用限制條件為徑長(zhǎng)的例子來(lái)說(shuō)明算法:仍用上圖仍用上圖,要求徑的長(zhǎng)度小于要求徑的長(zhǎng)度小于M(=7)的可用徑的可用徑.1)用用F算法求出圖的最短徑長(zhǎng)矩陣算法求出圖的最短徑長(zhǎng)矩陣W和轉(zhuǎn)接矩陣和轉(zhuǎn)接矩陣R;2)若若 ,則無(wú)可用徑則無(wú)可用徑, 若若 ,則找一個(gè)則找一個(gè) 的鄰接節(jié)點(diǎn)的鄰接節(jié)點(diǎn) ,如果如果 則排除則排除,否則就得一可用徑否則就得一可用徑MwstMwstsvivMwditsiitPis),(22本例的距離矩陣本例的距離矩陣, ,最

18、短路徑和轉(zhuǎn)接矩陣分別如下最短路徑和轉(zhuǎn)接矩陣分別如下011110550210103211302620122610D230030303300088888300312100830303338130010882000023813100038030200,0161413410525245650645321260413445440332125130233433320145242310RS)( , 862, 642)( , 716, 43155332211tstststswdwdwdwd是可用徑.再看V1與V3能否延續(xù)ttPsPs31) 3 ,( ,) 1 ,(24與與V1V1相連的有相連的有V2,V2,與

19、與V3V3相連的有相連的有V2.V2.)( , 711132, 611121, 6132, 4121424323421424121232323212121tststststststswdddvvvvvwdddvvvvwddvvvvwdd與與V2V2相連的有相連的有V4.V4.)( , 71132, 51121424323421424121tststswdddvvvvvwddd251v2v3v4v5v6vsvtv11111222335626(4)(4)圖的中心和中點(diǎn)圖的中心和中點(diǎn)從端間最短距離出發(fā)可定義網(wǎng)的從端間最短距離出發(fā)可定義網(wǎng)的中心中心, ,中點(diǎn)中點(diǎn)和和直徑直徑一個(gè)端一個(gè)端 在網(wǎng)內(nèi)的位置可用最長(zhǎng)的最短徑表示在網(wǎng)內(nèi)的位置可用最長(zhǎng)的最短徑表示: : 的最小值所對(duì)應(yīng)的端定義為網(wǎng)的中心的最小值所對(duì)應(yīng)的端定義為網(wǎng)的中心: :網(wǎng)的網(wǎng)的中點(diǎn)中點(diǎn)可定義為平均最短徑長(zhǎng)最小的端可定義為平均最短徑長(zhǎng)最小的端: :ijjiwMaxt ivit*iiitMint ,*iiijijisMinsws27網(wǎng)的直徑網(wǎng)的直徑: :例例1