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

1、《計(jì)量地理學(xué)》（徐建華，高等教育出版社，2005）配套實(shí)習(xí)指導(dǎo)13919.利用Matlab編程計(jì)算最短路徑及中位點(diǎn)選址1、最短路問(wèn)題兩個(gè)指定頂點(diǎn)之間的最短路徑。例如，給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖相應(yīng)兩頂點(diǎn)間的邊，GG得圖。對(duì)的每一邊，賦以一個(gè)實(shí)數(shù)—直通鐵路的長(zhǎng)度，稱為的權(quán)，GGe)(ewe得到賦權(quán)圖。的子圖的權(quán)是指子圖的各邊的權(quán)和。問(wèn)題就是求

2、賦權(quán)圖中GGG指定的兩個(gè)頂點(diǎn)間的具最小權(quán)的軌。這條軌叫做間的最短路，它的00vu00vu權(quán)叫做間的距離，亦記作。00vu)(00vud求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠(yuǎn)為順序，依次求得到的各頂點(diǎn)的最短路和距離，直至（或0u0uG0v直至的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用了G標(biāo)號(hào)算法。下面是該算法。(i)令，對(duì)，令，，。0)(0?ul0uv???)(vl00uS

3、?0?i(ii)對(duì)每個(gè)（），用iSv?iiSVS?)()()(minuvwulvliSu??代替。計(jì)算，把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，令)(vl)(minvliSv?1?iu《計(jì)量地理學(xué)》（徐建華，高等教育出版社，2005）配套實(shí)習(xí)指導(dǎo)141存放由始點(diǎn)到第點(diǎn)最短通路的值。)(idi求第一個(gè)城市到其它城市的最短路徑的Matlab程序如下：clearclcM=10000a(1:)=[050M402510]a(2:)=[zeros(12)1

4、520M25]a(3:)=[zeros(13)1020M]a(4:)=[zeros(14)1025]a(5:)=[zeros(15)55]a(6:)=zeros(16)a=aapb(1:length(a))=0pb(1)=1d(1:length(a))=Md(1)=0temp=1whilesum(pb)length(a)tb=find(pb==0)d(tb)=min(d(tb)d(temp)a(temptb))tmpb=find(d(t

5、b)==min(d(tb)))temp=tb(tmpb(1))pb(temp)=1endd運(yùn)行輸出，第一個(gè)城市到其它城市的最短路徑長(zhǎng)度，即：d=035453525102、選址問(wèn)題－以中位點(diǎn)選址為例中位點(diǎn)選址問(wè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(vi)（i=1，2，…，7），以及各鄉(xiāng)鎮(zhèn)之間的距離wij（i，j