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

§19.利用Matlab编程计算最短路径及中

位点选址1、最短路问题两个指定顶点之间的最短路径。例如，给出了一个连接若十个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)一直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u,v间的具最小权的轨。这条轨叫做u,v间的最短路，它的权0 0 0 0叫做u,v间的距离，亦记作d(u,v)。00 00求最短路已有成熟的算法：迪克斯特拉(Dijkstra)算法，其基本思想是按距u0从近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至V0(或直至G的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。令l(u)=0，对v。u，令l(v)=8，S={u}，i-0。0 0 0 0对每个veS(S=V\S)，用min{l(v),l(u)+w(uv)}ueSi代替l(v)。计算min{l(v)}，把达到这个最小值的一个顶点记为u1，令S广Su{u+11。(iii).若i=\VI—1，停止；若i<1VI—1，用i+1代替i，转(ii)。算法结束时，从u0到各顶点V的距离由V的最后一次的标号l(v)给出。在v进入Si之前的标号l(v)叫T标号，V进入Sj时的标号l(v)叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，u0至各项点的最短路也在图上标示出来了。例1：某公司在六个城市十◎…，C中有分公司，从C到七的直接航程票价记在下述矩阵的3")位置上。(8表示无直接航路)，请帮助该公司设计一张城市C1到其它城市间的票价最便宜的路线图。050840251050015208258150102084020100102525820100551025825550用矩阵气“(n为顶点个数)存放各边权的邻接矩阵，行向量pb、index1、index2、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量[1当第i顶点已标号Pb(i)=・ . ；〔°当第i顶点未标号index(i)存放始点到第i点最短通路中第i顶点前一顶点的序号；d(i)存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的Matlab程序如下：clear;clc;M=10000;a(1,:)=[0,50,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(1));pb(temp)=1;endd运行输出，第一个城市到其它城市的最短路径长度，即：d=0 35 45 35 25 102、选址问题一以中位点选址为例中位点选址问题的质量判据为：使最佳选址为止所在的定点到网络图中其他顶点的最短路径距离的总和(或者以各个顶点的载荷加权求和)达到最小。例2:某县下属七个乡镇，各乡镇所拥有的人口数a(v.)(i=1，2,…，7)，以及各乡镇之间的距离w..(i，j=1，2,…，7)如图所示。现在需要设立一个中i心邮局，为全县所辖的七个乡镇共同服务。试问该中心邮局应该设在哪一个乡镇

(图中的哪一个顶点)？图9.2.3第一步，用标号法求出每一个顶点vi至其它各个顶点刀的最短路径长度d登(i,j=1,2，…，7),并将其写成如下距离矩阵：rddddddd)11121314151617ddddddd21222324252627ddddddd31323334353637D=ddddddd41424344454647ddddddd51525354555657ddddddd616263646566671ddddddd1'71727374757677第二步，以各顶点的载荷(人口数)加权，求每一个顶点至其它各个顶点的最短路径长度的加权和，可在Matlab环境下用矩阵运算求得：定义各顶点的载荷矩阵：A=[a(v),a(v),a(v),a(v),a(v),a(v),a(v)]=[3,2.7.1.5.1.4]1 2 3 4 5 6 7S=[S(v),S(v),S(v),S(v),S(v),S(v),S(v)]=D*A1234567输出结果：s第三步，判断min{第三步，判断min{S(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(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