最短路問題的Bellman-Ford算法(2)

1、第第1頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第2頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法(荷蘭荷蘭:標(biāo)號(hào)法標(biāo)號(hào)法) 逐步逼近算法逐步逼近算法(Ford(Ford(美國美國) )算法算法):):修正標(biāo)號(hào)法修正標(biāo)號(hào)法 路矩陣算法路矩陣算法(Floyd(Floyd(佛洛伊德佛洛伊德) )算法算法)第第3頁頁逐次逼近算法思想逐次逼近算法思想 )1(11)(1ijkinikjwPMinP該公式表明，該公式表明， P(1)1j中的第中的第j個(gè)分量等于個(gè)分量等于P(0)1j的分量與基的分量與基本表本表(權(quán)

2、矩陣權(quán)矩陣)中的第中的第j列相應(yīng)元素路長的最小值，列相應(yīng)元素路長的最小值，它相當(dāng)它相當(dāng)于在于在v1與與vj之間插入一個(gè)轉(zhuǎn)接點(diǎn)之間插入一個(gè)轉(zhuǎn)接點(diǎn)(v1,v2,vn中的任一個(gè)，中的任一個(gè)，含點(diǎn)含點(diǎn)v1與與vj)后所有可能路中的最短路的路長；每迭代一后所有可能路中的最短路的路長；每迭代一次，就相當(dāng)與增加一個(gè)轉(zhuǎn)接點(diǎn)，而次，就相當(dāng)與增加一個(gè)轉(zhuǎn)接點(diǎn)，而P(k)1j中的每一個(gè)分量中的每一個(gè)分量則隨著則隨著k的增加而呈不增的趨勢(shì)！的增加而呈不增的趨勢(shì)！v1v2v312-3( )(1)11kkjjPP(0)11jjPw第第4頁頁用于計(jì)算帶有用于計(jì)算帶有負(fù)權(quán)弧負(fù)權(quán)弧指定點(diǎn)指定點(diǎn)v1 1到其余各點(diǎn)到其余各點(diǎn)的最短路

3、的最短路)1(11)(1ijkinikjwPMinPj=1,2,n. k=1,2,tn.2.2.計(jì)算計(jì)算逐次逼近算法基本步驟逐次逼近算法基本步驟(0)11jjPw j=1,2,n.1.1.令令(k)(1)11kjjPP其元素即是其元素即是v1 1到到vj j的最短路長。的最短路長。3.3.當(dāng)出現(xiàn)當(dāng)出現(xiàn)時(shí)，時(shí)，v1v2v312-3例例 計(jì)算從計(jì)算從點(diǎn)點(diǎn)v1 1到所有其它頂點(diǎn)的最短路到所有其它頂點(diǎn)的最短路解：初始條件為解：初始條件為 0000111213140,2,5,3PPPP 以后按照公式以后按照公式 進(jìn)行迭代。進(jìn)行迭代。 直到得到直到得到 ，迭代停止。，迭代停止。v1v2v3v4v6v5v8

4、v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP) 1(1)(1tjtjPP(0)11jjPwv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-20420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002

5、123031236612368791236810123653利用利用下標(biāo)下標(biāo)追蹤追蹤路徑路徑)1(11)(1ijkinikjwPMinP基本表基本表空格為無窮大空格為無窮大P1j表示從第一個(gè)頂點(diǎn)v1到其余各個(gè)頂點(diǎn)的最短路,(0)表示迭代次數(shù),表示最多經(jīng)過中轉(zhuǎn)的次數(shù)第第7頁頁v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-2042000253021230312561361102123031256123661368

6、1502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用利用下標(biāo)下標(biāo)追蹤追蹤路徑路徑)1(11)(1ijkinikjwPMinP基本表基本表空格為無窮大空格為無窮大第第8頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第9頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第10頁頁 某些問題需要求網(wǎng)絡(luò)上某些問題

7、需要求網(wǎng)絡(luò)上任意兩點(diǎn)任意兩點(diǎn)間的最間的最短路。當(dāng)然，它也可以用標(biāo)號(hào)算法依次改變短路。當(dāng)然，它也可以用標(biāo)號(hào)算法依次改變始點(diǎn)的辦法來計(jì)算，但是比較麻煩。始點(diǎn)的辦法來計(jì)算，但是比較麻煩。 這里介紹這里介紹FloydFloyd在在19621962年提出的年提出的路矩陣法路矩陣法，它可直接求出網(wǎng)絡(luò)中它可直接求出網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。任意兩點(diǎn)間的最短路。FloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第11頁頁 考慮考慮D D中任意兩點(diǎn)中任意兩點(diǎn)vi i，vj j，如將，如將D D中中vi i，vj j以外的點(diǎn)都刪掉，以外的點(diǎn)都刪掉，得只剩得只剩vi i，vj j的一個(gè)子網(wǎng)絡(luò)的一個(gè)子

8、網(wǎng)絡(luò)D D0 0，記，記ij(0)ij ,A ijwv vd當(dāng)否wijij為?。榛。?vi i，vj）的權(quán)。）的權(quán)。 在在D D0 0中加入中加入v1 1及及D D中與中與vi i，vj j，v1 1相關(guān)聯(lián)的弧，相關(guān)聯(lián)的弧，得得D D1 1，D D1 1中中vi i到到vj j的最短路記為的最短路記為 , ,則一定有則一定有(1)ijd(1)(0)(0)(0)i11j min, ijijddddvivjv1wijFloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想 網(wǎng)絡(luò)網(wǎng)絡(luò)D=D=（V V，A A，W W），令），令U=(U=(d dijij) )n n n n， 表示表示D D

9、中中vi i到到vj j的最的最短路的長度。短路的長度。dij第第12頁頁 再在再在D D1 1中加入中加入v2 2及及D D中與中與vi，vj，v1， v2相關(guān)聯(lián)的弧，得相關(guān)聯(lián)的弧，得D D2 2，D D2 2中中vi到到vj的最短路長記為的最短路長記為 ，則有，則有(2)ijd(2)(1)(1)(1)iji22 j min, ijddddFloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想(1)(0)(0)(0)i11j min, ijijdddd第第13頁頁FloydFloyd算法算法( (路矩陣法路矩陣法) )步驟步驟設(shè)有有向網(wǎng)絡(luò)設(shè)有有向網(wǎng)絡(luò)D=D=（V V，A A），其權(quán)

10、矩陣為），其權(quán)矩陣為A=(A=(aijij) )n nn n，AvvjiAvvwajijiijij),( , 0),( ,如下構(gòu)造如下構(gòu)造路矩陣序列路矩陣序列：則則n n階路矩陣階路矩陣D D( (n)n)中的元素中的元素d d(n)(n)ijij就是就是vi i到到vj j的最短路的路長。的最短路的路長。 令權(quán)矩陣令權(quán)矩陣A A為初始路矩陣為初始路矩陣D D（0 0），），即令即令D D（0 0）=A=A2. 2. 依次計(jì)算依次計(jì)算K K階路矩陣階路矩陣D D（K K）= =（d(k)(k)ijij）n nn n, k=1,2, k=1,2, ,n n，,) 1() 1() 1()(kkjk

11、ikkijkijdddMind這里這里第第14頁頁路矩陣序列的含義路矩陣序列的含義 K K階路矩陣階路矩陣D D（K K） 其中的元素表示相應(yīng)兩點(diǎn)間可能以點(diǎn)其中的元素表示相應(yīng)兩點(diǎn)間可能以點(diǎn)v1、v2、vk為為 轉(zhuǎn)接點(diǎn)的所有路中路長最短的路的路長。轉(zhuǎn)接點(diǎn)的所有路中路長最短的路的路長。 D（0） 其其中的任一元素表示相應(yīng)兩點(diǎn)間無轉(zhuǎn)接點(diǎn)時(shí)最短路路長。中的任一元素表示相應(yīng)兩點(diǎn)間無轉(zhuǎn)接點(diǎn)時(shí)最短路路長。一階路矩陣一階路矩陣D D（1 1） 其中的其中的元素表示相應(yīng)兩點(diǎn)間可能以點(diǎn)元素表示相應(yīng)兩點(diǎn)間可能以點(diǎn)v v1 1為轉(zhuǎn)接點(diǎn)的所有為轉(zhuǎn)接點(diǎn)的所有路中路長最短的路的路長；路中路長最短的路的路長；為使計(jì)算程序化，

12、轉(zhuǎn)接點(diǎn)按為使計(jì)算程序化，轉(zhuǎn)接點(diǎn)按頂點(diǎn)下標(biāo)的順序頂點(diǎn)下標(biāo)的順序依次加入依次加入n n階路矩陣階路矩陣D D( (n)n) 其中的元素其中的元素d d(n)(n)ijij就是就是vi到到vj的可能以點(diǎn)的可能以點(diǎn)v1、v2、vn為為轉(zhuǎn)接點(diǎn)的所有路中路長最短的路的路長。既是轉(zhuǎn)接點(diǎn)的所有路中路長最短的路的路長。既是vi到到vj的最的最短路的路長。短路的路長。第第15頁頁例例 求如下交通網(wǎng)絡(luò)中求如下交通網(wǎng)絡(luò)中各對(duì)點(diǎn)間最短路路長各對(duì)點(diǎn)間最短路路長。051250 102 A2302826042440該圖的權(quán)矩陣為該圖的權(quán)矩陣為：FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例31025v4v1

13、v2v5v312262448第第16頁頁例例 求如下交通網(wǎng)絡(luò)中求如下交通網(wǎng)絡(luò)中各對(duì)點(diǎn)間最短路路長各對(duì)點(diǎn)間最短路路長。FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例 0051250 102 D =A230282604244031025v4v1v2v5v312262448 0051250 102 D =A2302826042440(1)(0)(0)(0)i11j min, ijijdddd利用公式利用公式發(fā)現(xiàn)發(fā)現(xiàn)第一行，第一列元素不變第一行，第一列元素不變 105125 D220213621472302841274133042440031025v4v1v2v5v312262448

14、 105125 D2202136214723028412741330424400(2)(1)(1)(1)i22j min, ijijdddd利用公式利用公式發(fā)現(xiàn)發(fā)現(xiàn)第二行，第二列元素不變第二行，第二列元素不變 255 D02136234127221472147023255413344400121257202521731025v4v1v2v5v312262448 255 D0213621472302325541274133042440012214712572025217(3)(2)(2)(2)i33j min, ijijdddd利用公式利用公式發(fā)現(xiàn)發(fā)現(xiàn)第三行，第三列元素不變第三行，第三列元素不變

15、 3 D2136323255413341200132421325652147224132604531624031025v4v1v2v5v312262448002147204127042400221471257 3 D213632325541334120013242132565021472241326045316240 4 D0213623032552011325/1456202413264133440221472531/5416413245(4)(3)(3)(3)i44j min, ijijdddd利用公式利用公式發(fā)現(xiàn)發(fā)現(xiàn)第四行，第四列元素不變第四行，第四列元素不變31025v4v1v2v5v

16、31226244831025v4v1v2v5v312262448 4 D021362147230325502401202413264133440221472531/54164132451325/1456D(5)中的元素給出相應(yīng)兩點(diǎn)間中的元素給出相應(yīng)兩點(diǎn)間的最短路，其下標(biāo)給出最短路的最短路，其下標(biāo)給出最短路個(gè)頂點(diǎn)下標(biāo)個(gè)頂點(diǎn)下標(biāo),比如：比如： 5 D021362147230325502401202413264133440221472531/54164132451325/14566254第第22頁頁已知有已知有7 7個(gè)村子，相互間道路的距離如下圖示。擬合建一所個(gè)村子，相互間道路的距離如下圖示。擬合建

17、一所小學(xué)，已知小學(xué)，已知A A處有小學(xué)生處有小學(xué)生3030人，人，B B處處4040人，人，C C處處2525人，人，D D處處2020人，人，E E處處5050人，人，F(xiàn) F處處6060人，人， G處處60人人,問小學(xué)應(yīng)建在哪一個(gè)村子，問小學(xué)應(yīng)建在哪一個(gè)村子，使學(xué)生上學(xué)最方便（使學(xué)生上學(xué)最方便（原則所有人走的總路程最短；盡可原則所有人走的總路程最短；盡可能公平。）。能公平。）。最短路問題算例最短路問題算例1(1(選址問題選址問題) )AGFECB522747163D26第第23頁頁 0052502 72074 D270 6 276 0 1 342 1 0 63 6 0A 最短路問題算例最短路

18、問題算例1(1(選址問題選址問題) )AGFECB522747163D26第第24頁頁 21331210525072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 最短路問題算例最短路問題算例1(1(選址問題選址問題) ) 0052502 72074 D270 6 276 0 1 342 1 0 63 6 0A 12412521331220527125072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 21331210525072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 1241251362132

19、13631213253421521521363163205271265072 7 112707 144 D7270 6 2127146 0 1 361142 1 0 63 6 0 12412521331220527125072 72 7074 D270 6 276 0 1 342 1 0 63 6 0 12412513621324631213254421521521363163205271265072 7 42707 144 D7270 6 2127146 0 1 36442 1 0 63 6 0 124125136213213631213253421521521363163205271265

20、072 7 112707 144 D7270 6 2127146 0 1 361142 1 0 63 6 0 12412513612547213246257312132513257542145752152136316326577521752752137547560527126155072 7 4102707 144 17 D727026912714610364420141510179430 12412513621324631213254421521521363163205271265072 7 42707 144 D7270 6 2127146 0 1 36442 1 0 63 6 0 124

21、13651361365721324652462465731236436536576421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201410886430 12412513612547213246257312132513257542145752152136316326577521752752137547560527126155072 7 4102707 144 17 D727026912714610364420141510179430 1241

22、3651361365721324652462465731236436536576421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201410886430 12413651361365721324652462465731236436536577421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201

23、410886430 12413651361365721324652462465731236436536577421463465465756315462563564631632657756317564275637564756052776105072 548270654 8 D72602367553103644201410886430A A處處3030人，人，B B處處4040人，人，C C處處2525人，人，D D處處2020人，人，E E處處5050人，人，F(xiàn) F處處6060人，人， G G處處6060人人. .02005014035036060015001754025024048060280

24、0120250240480210801500150120360210200125600601801801601004050024030032020012025024001700 1335 1430 1070 835 1330A B C D E F GABCDEFG第第32頁頁某工廠使用一臺(tái)設(shè)備，每年年初工廠都要作出決定：如果繼某工廠使用一臺(tái)設(shè)備，每年年初工廠都要作出決定：如果繼續(xù)使用舊的，要付維修費(fèi)；如果買新的，要付購置費(fèi)。試制續(xù)使用舊的，要付維修費(fèi)；如果買新的，要付購置費(fèi)。試制定一個(gè)五年更新計(jì)劃，使工廠總支出最少？定一個(gè)五年更新計(jì)劃，使工廠總支出最少？若該設(shè)備在各年的購置費(fèi)、不同役齡的殘值及

25、維修費(fèi)如下表：若該設(shè)備在各年的購置費(fèi)、不同役齡的殘值及維修費(fèi)如下表：項(xiàng)目項(xiàng)目購置費(fèi)購置費(fèi)設(shè)備役齡設(shè)備役齡維修費(fèi)維修費(fèi)殘值殘值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年 11 0- -1 5 4 12 1- -2 6 3 13 2- -3 8 2 14 3- -4 11 1 15 4- -5 18 0 最短路問題算例最短路問題算例2(2(設(shè)備更新問題設(shè)備更新問題) )第第33頁頁最短路問題算例最短路問題算例2(2(設(shè)備更新問題設(shè)備更新問題) )項(xiàng)目項(xiàng)目購置費(fèi)購置費(fèi)設(shè)備役齡設(shè)備役齡維修費(fèi)維修費(fèi)殘值殘值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年 11 0- -1 5 4