利用Matlab编程计算最短路径及中位点选址
§19.利用Mat lab编程计算最短路径及中位点选址1、最短路问题两个指定顶点之间的最短路径。例如，给出了一个连接若十个城镇的铁路网络，在这个网络的两个指定城镇 间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边， 得图G。对G的每一边e，赋以一个实数w(e)一直通铁路的长度，称为e的权， 得到赋权图G。 G的子图的权是指子图的各边的权和。问题就是求赋权图G中 指定的两个顶点u ,v间的具最小权的轨。这条轨叫做u ,v间的最短路，它的权 0000叫做u , v间的距离，亦记作d(u , v )。0000求最短路已有成熟的算法：迪克斯特拉(Dijkstra)算法，其基本思想是按 距U0从近到远为顺序，依次求得U0到弓的各顶点的最短路和距离，直至V0 (或 直至G的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采用了 标号算法。下面是该算法。(i) 令 l(u ) = 0，对 v。u，令 l(v) = 8，S = u ，i - 0。0000(ii) 对每个 v e S ( S = V Si)，用minl (v), l (u) + w(uv) ueSi代替l(v)。计算minl(v)，把达到这个最小值的一个顶点记为 u+1，令S 广 S u u +11。(iii).若 i=W I1，停止；若 i <1V I1，用 i +1 代替 i，转(ii)。算法结束时，从u0到各顶点u的距离由u的最后一次的标号I(v)给出。在v进 入Si之前的标号1 (v)叫T标号，v进入Si时的标号l(v)叫P标号。算法就是不断 修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获 得P标号所由来的边在图上标明，则算法结束时，U0至各项点的最短路也在图 上标示出来了。例1：某公司在六个城市十，C中有分公司，从C到七的直接航程票 价记在下述矩阵的3")位置上。(8表示无直接航路)，请帮助该公司设计一张 城市C1到其它城市间的票价最便宜的路线图。050840251050015208258150102084020100102525820100551025825550用矩阵气“顷为顶点个数)存放各边权的邻接矩阵，行向量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;while sum(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 =035453525102、选址问题一以中位点选址为例中位点选址问题的质量判据为：使最佳选址为止所在的定点到网络图中其他 顶点的最短路径距离的总和(或者以各个顶点的载荷加权求和)达到最小。例2:某县下属七个乡镇，各乡镇所拥有的人口数a(v)(i=1，2,，7)，以及各乡镇之间的距离w.(i，j=1，2,，7)如图所示。现在需要设立一个中i心邮局，为全县所辖的七个乡镇共同服务。试问该中心邮局应该设在哪一个乡镇(图中的哪一个顶点)？图9.2.3第一步，用标号法求出每一个顶点vi至其它各个顶点vj的最短路径长度d登（i, j = 1, 2，7）,并将其写成如下距离矩阵:r ddddddd ）11121314151617ddddddd21222324252627ddddddd31323334353637D =ddddddd41424344454647ddddddd51525354555657ddddddd616263646566671 ddddddd 1' 71727374757677第二步，以各顶点的载荷(人口数)加权，求每一个顶点至其它各个顶点的 最短路径长度的加权和，可在Matlab环境下用矩阵运算求得：定义各顶点的载荷矩阵：A = a(v ),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输出结果：s第三步，判断minS (v ).ii计算如下:第一步:clear;clc;M=10000;for i=1:length(a)pb(1:length(a)=0;pb(i)=1; d(1:length(a)=M;d(i)=0;temp=i;while sum(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=3 2 7 1 5 1 4;S= ShortPath * A'运行后输出S，即每一个顶点至其它各个顶点的最短路径长度的加权和:S =122.300071.300069.500069.5000108.500072.800095.3000第三步：min（S）运行后输出S的最小值：ans =69.5000判断：因为s （叩=S叩5邮气） = 69.5。所以，如七都是图9.2.3 的中位点。也就是说，中心邮局设在寸3或巳都是可行的。
