利用Matlab编程计算最短路径及中位点选址

1、2 计量地理学(徐建华，高等教育出版社，2005)配套实习指导i 利用编程计算最短路径及中位点选址1最短路问题两个指定顶点之间的最短路径。例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e,赋以一个实数w(e)直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u,v间的具最小权的轨。这条轨叫做u,v间的最短路，它的权0000叫做u,v间的距离，亦记作d(u,v)。0000求最短路已有成熟的算法：迪克斯特拉(Dij

2、kstra)算法，其基本思想是按距u从近到远为顺序，依次求得u到G的各顶点的最短路和距离，直至v(或000直至G的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。令l(u)0，对v丰u，令/(v),，Su，i=0。0000对每个veS(S=VS)，用iiiminl(v),l(u)w(uv)ueSi代替l(v)。计算min/(v)，把达到这个最小值的一个顶点记为u，令veSi1S二sui1ii1。(iii).若i=1VI，1，停止；若i1VI，1，用i1代替i，转(ii)。算法结束时，从u0到各顶点v的距离由v的最后一次的标号1(v)给出。在v进入Si之前的

3、标号1(v)叫T标号，v进入Si时的标号1(v)叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，uo至各项点的最短路也在图上标示出来了。例1某公司在六个城市crc2,c中有分公司，从c到cj的直接航程票价记在下述矩阵的(i,力位置上。(表示无直接航路)，请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。050402510500152025150102040201001025252010055102525550用矩阵a(n为顶点个数)存放各边权的邻接矩阵，行向量、index、nn1index、d分别

4、用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路2的值。其中分量pb(i)二当第i顶点已标号当第i顶点未标号2 #计量地理学(徐建华，高等教育出版社，2005)配套实习指导i #2 #计量地理学(徐建华，高等教育出版社，2005)配套实习指导i #index(i)存放始点到第i点最短通路中第i顶点前一顶点的序号;计量地理学(徐建华，高等教育出版社，2005)配套实习指导 计量地理学(徐建华，高等教育出版社，2005)配套实习指导i #d(i)存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的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运行输出，第一个城市到其它城市的最短路径长度，即：d=035453525102、选址问题以中位点选址为例中位点选址问题的质量判据为：使最佳选址为止所在的定点到网络图中其他顶点的最短路径距离的总和(或者以各个顶点的载荷加权求和)达到最小。例2某县下属七个乡镇，各乡镇所拥有的人口数a(v)(i=1,2，7)，以及各乡镇之间的距离w.(i,j=1,2,，7)如图所示。现在需要设立一个中IJJ心邮局，为全县所辖的七个乡镇共同服务。试问该中心邮局应该设在哪一个乡镇图中的哪一个顶点)？3a(v5)=Sa(V7)=4a(v3)=?a(v4)=la(vi)=33a(v6)=

7、la(v2)=2图9.2.3第一步，用标号法求出每一个顶点vi至其它各个顶点vj的最短路径长度d,j=1,2，7),并将其写成如下距离矩阵：ddddddd,ii121314151617ddddddd21222324252627ddddddd31323334353637D=ddddddd41424344454647ddddddd51525354555657ddddddd61626364656667ddddddd.71727374757677第二步，以各顶点的载荷(人口数)加权，求每一个顶点至其它各个顶点的最短路径长度的加权和，可在Matlab环境下用矩阵运算求得：定义各顶点的载荷矩阵：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输出结果：SminS(v)第三步，判断ii计算如下：第一步：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;运行后输出最短距离矩阵，即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;运行后输出S,即每一个顶点至其它各个顶点的最短路径长度的加权和:S=122.3