利用matlab編程計算最短路徑及中位點選址

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

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

3、?0?i(ii)對每個（），用iSv?iiSVS?)()()(minuvwulvliSu??代替。計算，把達到這個最小值的一個頂點記為，令)(vl)(minvliSv?1?iu《計量地理學(xué)》（徐建華，高等教育出版社，2005）配套實習(xí)指導(dǎo)141存放由始點到第點最短通路的值。)(idi求第一個城市到其它城市的最短路徑的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運行輸出，第一個城市到其它城市的最短路徑長度，即：d=035453525102、選址問題－以中位點選址為例中位點選址問題的質(zhì)量判據(jù)為：使最佳選址為止所在的定點到網(wǎng)絡(luò)圖中其他頂點的最短路徑距離的總和（或者以各個頂點的載荷加權(quán)求和）達到最小。例2：某縣下屬七個鄉(xiāng)鎮(zhèn)，各鄉(xiāng)鎮(zhèn)所擁有的人口數(shù)a(vi)（i=1，2，…，7），以及各鄉(xiāng)鎮(zhèn)之間的距離wij（i，j