matlab最短路径
§19. 利用Matlab编程计算最短路径及中
位点选址
1、最短路问题
两个指定顶点之间的最短路径。
例如,给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,找一条最短铁路线。
以各城镇为图G的顶点,两城镇间的直通铁路为图G相应两顶点间的边,得图G。对G的每一边e,赋以一个实数w(e)—直通铁路的长度,称为e的权,得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u0,v0间的具最小权的轨。这条轨叫做u0,v0间的最短路,它的权叫做u0,v0间的距离,亦记作d(u0,v0)。
求最短路已有成熟的算法:迪克斯特拉(Dijkstra)算法,其基本思想是按距u0从近到远为顺序,依次求得u0到G的各顶点的最短路和距离,直至v0(或直至G的所有顶点),算法结束。为避免重复并保留每一步的计算信息,采用了标号算法。下面是该算法。
(i) 令l(u0)0,对vu0,令l(v),S0{u0},i0。
(ii) 对每个vi(iV\Si),用
min{l(v),l(u)w(uv)}
uSi
代替l(v)。计算{l(v)},把达到这个最小值的一个顶点记为ui1,令
vi
139
Si1Si{ui1}。
(iii). 若i|V|1,停止;若i|V|1,用i1代替i,转(ii)。
算法结束时,从u0到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入Si之前的标号l(v)叫T标号,v进入Si时的标号l(v)叫P标号。算法就是不断修改各项点的T标号,直至获得P标号。若在算法运行过程中,将每一顶点获得P标号所由来的边在图上标明,则算法结束时,u0至各项点的最短路也在图上标示出来了。
例1: 某公司在六个城市c1,c2,,c6中有分公司,从ci到cj的直接航程票
价记在下述矩阵的(i,j)位置上。(表示无直接航路),请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。
0
50402510
402510
0152025
1501020
2010010252010055
252555050
用矩阵ann(n为顶点个数)存放各边权的邻接矩阵,行向量pb、index1、
index2、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量
1当第i顶点已标号
; pb(i)
0当第i顶点未标号
index2(i) 存放始点到第i点最短通路中第i顶点前一顶点的序号;
140
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)
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 d
运行输出,第一个城市到其它城市的最短路径长度,即:
d =
0 35 45 35 25 10
2、选址问题-以中位点选址为例
中位点选址问题的质量判据为:使最佳选址为止所在的定点到网络图中其他顶点的最短路径距离的总和(或者以各个顶点的载荷加权求和)达到最小。
例2:某县下属七个乡镇,各乡镇所拥有的人口数a(vi)(i=1,2,…,7),
以及各乡镇之间的距离wij(i,j=1,2,…,7)如图所示。现在需要设立一个中心邮局,为全县所辖的七个乡镇共同服务。试问该中心邮局应该设在哪一个乡镇
141
(图中的哪一个顶点)?
图9.2.3
第一步,用标号法求出每一个顶点vi至其它各个顶点vj的最短路径长度dij(i,j = 1,2,…,7),并将其写成如下距离矩阵:
d11
d21d31
Dd41
d51d61d71
d12d22d32d42d52d62d72
d13d23d33d43d53d63d73
d14d24d34d44d54d64d74
d15d25d35d45d55d65d75
d16d26d36d46d56d66d76
d17d27d37d47 d57d67d77
第二步,以各顶点的载荷(人口数)加权,求每一个顶点至其它各个顶点的最短路径长度的加权和,可在Matlab环境下用矩阵运算求得:
定义各顶点的载荷矩阵:
A[a(v1),a(v2),a(v3),a(v4),a(v5),a(v6),a(v7)][3,2.7.1.5.1.4] S[S(v1),S(v2),S(v3),S(v4),S(v5),S(v6),S(v7)]D*A
142
输出结果:S
第三步,判断mini
{S(vi)}
计算如下: 第一步:
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)
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;
运行后输出最短距离矩阵,即ShortPath
ShortPath =
0 3.0000 5.0000 6.3000 9.3000 4.5000 6.0000 3.0000 0 2.0000 3.3000 6.3000 1.5000 3.0000 5.0000 2.0000 0 2.0000 5.0000 3.5000 5.0000 6.3000 3.3000 2.0000 0 3.0000 1.8000 3.3000 9.3000 6.3000 5.0000 3.0000 0 4.8000 6.3000 4.5000 1.5000 3.5000 1.8000 4.8000 0 1.5000 6.0000 3.0000 5.0000 3.3000 6.3000 1.5000 0
第二步:
A=[3 2 7 1 5 1 4]; S= ShortPath * A';
143
运行后输出S,即每一个顶点至其它各个顶点的最短路径长度的加权和:
S =
122.3000 71.3000 69.5000 69.5000 108.5000 72.8000 95.3000
第三步:
min(S)
运行后输出S的最小值:
ans =
69.5000
判断:因为S(v3)S(v4)min{S(vi)}69.5。所以,v3和v4都是图9.2.3
i
的中位点。也就是说,中心邮局设在v3或v4都是可行的。
144