利用Matlab編程計(jì)算最短路徑及中位點(diǎn)選址

1、2 計(jì)量地理學(xué)(徐建華，高等教育出版社，2005)配套實(shí)習(xí)指導(dǎo)i 利用編程計(jì)算最短路徑及中位點(diǎn)選址1最短路問題兩個(gè)指定頂點(diǎn)之間的最短路徑。例如，給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩頂點(diǎn)間的邊，得圖G。對G的每一邊e,賦以一個(gè)實(shí)數(shù)w(e)直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖G中指定的兩個(gè)頂點(diǎn)u,v間的具最小權(quán)的軌。這條軌叫做u,v間的最短路，它的權(quán)0000叫做u,v間的距離，亦記作d(u,v)。0000求最短路已有成熟的算法：迪克斯特拉(Dij

2、kstra)算法，其基本思想是按距u從近到遠(yuǎn)為順序，依次求得u到G的各頂點(diǎn)的最短路和距離，直至v(或000直至G的所有頂點(diǎn))，算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號算法。下面是該算法。令l(u)0，對v豐u，令/(v),，Su，i=0。0000對每個(gè)veS(S=VS)，用iiiminl(v),l(u)w(uv)ueSi代替l(v)。計(jì)算min/(v)，把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為u，令veSi1S二sui1ii1。(iii).若i=1VI，1，停止；若i1VI，1，用i1代替i，轉(zhuǎn)(ii)。算法結(jié)束時(shí)，從u0到各頂點(diǎn)v的距離由v的最后一次的標(biāo)號1(v)給出。在v進(jìn)入Si之前的

3、標(biāo)號1(v)叫T標(biāo)號，v進(jìn)入Si時(shí)的標(biāo)號1(v)叫P標(biāo)號。算法就是不斷修改各項(xiàng)點(diǎn)的T標(biāo)號，直至獲得P標(biāo)號。若在算法運(yùn)行過程中，將每一頂點(diǎn)獲得P標(biāo)號所由來的邊在圖上標(biāo)明，則算法結(jié)束時(shí)，uo至各項(xiàng)點(diǎn)的最短路也在圖上標(biāo)示出來了。例1某公司在六個(gè)城市crc2,c中有分公司，從c到cj的直接航程票價(jià)記在下述矩陣的(i,力位置上。(表示無直接航路)，請幫助該公司設(shè)計(jì)一張城市c1到其它城市間的票價(jià)最便宜的路線圖。050402510500152025150102040201001025252010055102525550用矩陣a(n為頂點(diǎn)個(gè)數(shù))存放各邊權(quán)的鄰接矩陣，行向量、index、nn1index、d分別

4、用來存放P標(biāo)號信息、標(biāo)號頂點(diǎn)順序、標(biāo)號頂點(diǎn)索引、最短通路2的值。其中分量pb(i)二當(dāng)?shù)趇頂點(diǎn)已標(biāo)號當(dāng)?shù)趇頂點(diǎn)未標(biāo)號2 #計(jì)量地理學(xué)(徐建華，高等教育出版社，2005)配套實(shí)習(xí)指導(dǎo)i #2 #計(jì)量地理學(xué)(徐建華，高等教育出版社，2005)配套實(shí)習(xí)指導(dǎo)i #index(i)存放始點(diǎn)到第i點(diǎn)最短通路中第i頂點(diǎn)前一頂點(diǎn)的序號;計(jì)量地理學(xué)(徐建華，高等教育出版社，2005)配套實(shí)習(xí)指導(dǎo) 計(jì)量地理學(xué)(徐建華，高等教育出版社，2005)配套實(shí)習(xí)指導(dǎo)i #d(i)存放由始點(diǎn)到第i點(diǎn)最短通路的值。求第一個(gè)城市到其它城市的最短路徑的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50

5、,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a=a+a;pb(1:length(a)=0;pb(1)=1;d(1:length(a)=M;d(1)=0;temp=1;whilesum(pb)length(a)tb=find(pb=0);d(tb)=min(d(tb),d(temp)+a(temp,tb);tmpb=find(d(tb)=min(d(tb);temp=tb(tmpb(

6、1);pb(temp)=1;endd運(yùn)行輸出，第一個(gè)城市到其它城市的最短路徑長度，即：d=035453525102、選址問題以中位點(diǎn)選址為例中位點(diǎn)選址問題的質(zhì)量判據(jù)為：使最佳選址為止所在的定點(diǎn)到網(wǎng)絡(luò)圖中其他頂點(diǎn)的最短路徑距離的總和(或者以各個(gè)頂點(diǎn)的載荷加權(quán)求和)達(dá)到最小。例2某縣下屬七個(gè)鄉(xiāng)鎮(zhèn)，各鄉(xiāng)鎮(zhèn)所擁有的人口數(shù)a(v)(i=1,2，7)，以及各鄉(xiāng)鎮(zhèn)之間的距離w.(i,j=1,2,，7)如圖所示?，F(xiàn)在需要設(shè)立一個(gè)中IJJ心郵局，為全縣所轄的七個(gè)鄉(xiāng)鎮(zhèn)共同服務(wù)。試問該中心郵局應(yīng)該設(shè)在哪一個(gè)鄉(xiāng)鎮(zhèn)圖中的哪一個(gè)頂點(diǎn))？3a(v5)=Sa(V7)=4a(v3)=?a(v4)=la(vi)=33a(v6)=

7、la(v2)=2圖9.2.3第一步，用標(biāo)號法求出每一個(gè)頂點(diǎn)vi至其它各個(gè)頂點(diǎn)vj的最短路徑長度d,j=1,2，7),并將其寫成如下距離矩陣：ddddddd,ii121314151617ddddddd21222324252627ddddddd31323334353637D=ddddddd41424344454647ddddddd51525354555657ddddddd61626364656667ddddddd.71727374757677第二步，以各頂點(diǎn)的載荷(人口數(shù))加權(quán)，求每一個(gè)頂點(diǎn)至其它各個(gè)頂點(diǎn)的最短路徑長度的加權(quán)和，可在Matlab環(huán)境下用矩陣運(yùn)算求得：定義各頂點(diǎn)的載荷矩陣：A二a(v

8、),a(v),a(v),a(v),a(v),a(v),a(v)二3,2.7.1.5.1.41234567S二S(v),S(v),S(v),S(v),S(v),S(v),S(v)二D*A1234567輸出結(jié)果：SminS(v)第三步，判斷ii計(jì)算如下：第一步：clear;clc;M=10000;fori=1:length(a)pb(1:length(a)=0;pb(i)=1;d(1:length(a)=M;d(i)=0;temp=i;whilesum(pb)length(a)tb=find(pb=0);d(tb)=min(d(tb),d(temp)+a(temp,tb);tmpb=find(d(

9、tb)=min(d(tb);temp=tb(tmpb(1);pb(temp)=1;end;ShortPath(i,:)=d;end;ShortPath;運(yùn)行后輸出最短距離矩陣，即ShortPathShortPath=03.00005.00006.30009.30004.50006.00003.000002.00003.30006.30001.50003.00005.00002.000002.00005.00003.50005.00006.30003.30002.000003.00001.80003.30009.30006.30005.00003.000004.80006.30004.50001.50003.50001.80004.800001.50006.00003.00005.00003.30006.30001.50000第二步：A=3271514;S=ShortPath*A;運(yùn)行后輸出S,即每一個(gè)頂點(diǎn)至其它各個(gè)頂點(diǎn)的最短路徑長度的加權(quán)和:S=122.3