數(shù)學(xué)建模floyd算法最短路算法詳解ppt課件

1、最短路算法恣意一對頂點(diǎn)之間的最短路算法恣意一對頂點(diǎn)之間的最短路算法:Floyd:Floyd算法算法(二二)算算法法原原理理1、求間隔矩陣的方法、求間隔矩陣的方法2、求途徑矩陣的方法、求途徑矩陣的方法3、查找最短路途徑的方法、查找最短路途徑的方法一算法的根本思想一算法的根本思想三算法步驟三算法步驟算法的根本思想算法的根本思想 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出個(gè)矩陣 D(1)、 D(2)、 、D()，使最后得到的矩陣 D()成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑算法原理算法原理 求間隔矩陣的方法求間隔矩陣的方法把帶權(quán)鄰接矩陣 W 作為距離矩陣的初值，即 D

2、(0)=)()0(ijd=W（）D(1)= )() 1 (ijd，其中)0(1)0()1 (,miniijijddd)0(1jd) 1 (ijd是從 vi到 vj的只允許以 v1作為中間點(diǎn)的路徑中最短路的長度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd) 1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點(diǎn)的路徑中最短路的長度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點(diǎn)的路徑中最短路的長度即是從 vi到 vj中間可

3、插入任何頂點(diǎn)的路徑中最短路的長，因此D()即是距離矩陣算法原理算法原理 求途徑矩陣的方法求途徑矩陣的方法R=)(ijr, rij的含義是從 vi到 vj的最短路要經(jīng)過點(diǎn)號為 rij的點(diǎn))()0()0(ijrR, jrij)0(每求得一個(gè) D(k)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立間隔矩陣的同時(shí)可建立途徑矩陣R 即當(dāng)vk被插入任何兩點(diǎn)間的最短途徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來查找任何點(diǎn)對之間最短路的途徑)(D)(R)(Rij算法原理算法原理 查找最短路途徑的方法查找最短路途徑的方法然后用同樣

4、的方法再分頭查找若：（） 向點(diǎn) i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向點(diǎn) j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm那么由點(diǎn)i到j(luò)的最短路的途徑為：jqqqpppimk,21, 12算法步驟算法步驟Floyd算算法法：求任意兩點(diǎn)間的最短路D(i,j)：i 到j(luò) 的距離R(i,j)：i 到j(luò) 之間的插入點(diǎn)輸入: 帶權(quán)鄰接矩陣 w(i,j)（） 賦初值：對所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,j)對所有 i,j，若 d(i,k)+d(k,j)d(i,j

5、)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉(zhuǎn)（） 自定義自定義floyd函數(shù)函數(shù)function d,r=floyd(w)n=length(w);for i=1:n for j=1:n d(i,j)=w(i,j); r(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=k; end end endend5333434331543243332444441,064696024342025642079

6、3570RD951d，故從v5到v1的最短路為51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以從 v5到 v1的最短路徑為：1435.clear;w=0,9,inf,3,inf;9,0,2,inf,7;inf,2,0,2,4;3,inf,2,0,inf;inf,7,4,inf,0;d,r=floyd(w)（2） 計(jì)算在各點(diǎn)iv設(shè)立服務(wù)設(shè)施的最大服務(wù)距離)(ivS max)(1ijjidvS , 2 , 1i 選址問題-中心問題例例 2某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示問應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短（1）用 Floyd 算法求

7、出距離矩陣 D=)(ijd（3）求出頂點(diǎn)kv，使)(min)(1iikvSvS則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中中心心點(diǎn)點(diǎn)clear;w=0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0;d,r=floyd(w)S=max(d) %求矩陣各列的最大值s=min(S)05 .15 .55 .86475 .10475 .45

8、 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。 選址問題-重心問題例例 3某礦區(qū)有七個(gè)礦點(diǎn)，如圖所示已知各礦點(diǎn)每天的產(chǎn)礦量)(jvq（標(biāo)在圖的各頂點(diǎn)上） 現(xiàn)要從這七個(gè)礦點(diǎn)選一個(gè)來建造礦廠 問應(yīng)選在哪個(gè)礦點(diǎn)，才能使各礦點(diǎn)所產(chǎn)的礦運(yùn)到選礦廠所在地的總運(yùn)力（千噸公里）最?。?）求距離陣 D=)(ijd（2） 計(jì)算各頂點(diǎn)作為選礦廠的總運(yùn)力)(ivm ijjji

9、dvqvm)()(1 , 2 , 1i（3） 求kv使)(min)(1iikvmvm，則kv就是選礦廠應(yīng)設(shè)之礦點(diǎn)此點(diǎn)稱為圖 G 的重重心心或中中位位點(diǎn)點(diǎn)clear;w=0,3,inf,inf,inf,inf,inf;3,0,2,inf,inf,4,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,1,inf,inf;inf,inf,2,1,0,4,inf;inf,4,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0;d,r=floyd(w)q=3,2,7,1,6,1,4;for i=1:7 m1=0; for j=1:7 m1=m1+q(

10、j)*d(i,j); end m(i)=m1;endmmin(m)d = 0 3.0000 5.0000 8.0000 7.0000 7.0000 8.5000 3.0000 0 2.0000 5.0000 4.0000 4.0000 5.5000 5.0000 2.0000 0 3.0000 2.0000 6.0000 7.5000 8.0000 5.0000 3.0000 0 1.0000 5.0000 6.5000 7.0000 4.0000 2.0000 1.0000 0 4.0000 5.5000 7.0000 4.0000 6.0000 5.0000 4.0000 0 1.5000 8.5000 5.5000 7.5000 6.5000 5.5000 1.5000 0m =132 78 70 92 70 106 130ans =70實(shí)驗(yàn)八、最正確災(zāi)情巡視道路節(jié)選部分實(shí)驗(yàn)八、最正確災(zāi)情