logo资料库

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

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.07M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    实习指导 --《计量地理学》（徐建华，华东师范大学） §19. 利用 Matlab 编程计算最短路径及中 位点选址 1、最短路问题 两个指定顶点之间的最短路径。 例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇 间，找一条最短铁路线。 以各城镇为图 G 的顶点，两城镇间的直通铁路为图 相应两顶点间的边， G 得图G 。对G 的每一边 e ，赋以一个实数 )(ew —直通铁路的长度，称为 e 的权， 得到赋权图 。 的子图的权是指子图的各边的权和。问题就是求赋权图G 中 G G 指定的两个顶点 0,vu 0 间的具最小权的轨。这条轨叫做 0,vu 0 间的最短路，它的权 叫做 0,u v 0 间的距离，亦记作 0 vud , ( 0 ) 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按 距 从近到远为顺序，依次求得 到 的各顶点的最短路和距离，直至 （或 0u 0u G 0v 直至 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了 G 标号算法。下面是该算法。 (i) 令 ( 0 =ul ) 0 ，对 v ≠ 0u ，令 ∞=)(vl ， S = 0 u }{ 0 ， 0=i 。 (ii) 对每个 v ∈ （ iS S i = SV \ i ），用 ({min iSu ∈ ulvl )( ), + uvw ( )} 代替 。计算 )(vl )}({min iSv∈ vl ，把达到这个最小值的一个顶点记为 ，令1+iu 139
    实习指导 --《计量地理学》（徐建华，华东师范大学） S + = 1 i S i u { } i 1 + U 。 (iii). 若 = Vi | 1| − ，停止；若 < Vi | 1| − ，用 1+i 代替i ，转(ii)。 算法结束时，从 到各顶点 的距离由 的最后一次的标号 给出。在 进 )(vl v 0u v v iS )(vl 入 之前的标号 叫 T 标号，v 进入 时的标号 叫 P 标号。算法就是不断 修改各项点的 T 标号，直至获得 P 标号。若在算法运行过程中，将每一顶点获 )(vl iS 得 P 标号所由来的边在图上标明，则算法结束时， 至各项点的最短路也在图 0u 上标示出来了。 例 1： 某公司在六个城市 cc L , , 2 1 , c 6 中有分公司，从 到 的直接航程票 ic jc 价记在下述矩阵的 i j ),( 位置上。（ ∞ 表示无直接航路），请帮助该公司设计一张 城市 到其它城市间的票价最便宜的路线图。 1c 0 ⎡ ⎢ 50 ⎢ ∞ ⎢ ⎢ 40 ⎢ 25 ⎢ ⎢ 10 ⎣ 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 ⎤ ⎥ 25 ⎥ ∞ ⎥ ⎥ 25 ⎥ 55 ⎥ ⎥ 0 ⎦ 用矩阵 （ n 为顶点个数）存放各边权的邻接矩阵，行向量 、 pb nna × index 1 、 index 2 、d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路 的值。其中分量 ipb )( = 1 ⎧ ⎨ 0 ⎩ i 顶点已标号 当第 i 当第 顶点未标号 ； 存放始点到第 点最短通路中第 顶点前一顶点的序号； i i index )(2 i 140
    实习指导 --《计量地理学》（徐建华，华东师范大学） )(id 存放由始点到第 点最短通路的值。 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)
    实习指导 --《计量地理学》（徐建华，华东师范大学） （图中的哪一个顶点）？ 图9.2.3 第一步，用标号法求出每一个顶点vi至其它各个顶点vj的最短路径长度 dij（i，j ＝ 1，2，…，7），并将其写成如下距离矩阵： D = d d d d d d d 11 21 31 41 51 61 71 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ d d d d d d d 12 22 32 42 52 62 72 d d d d d d d 13 23 33 43 53 63 73 d d d d d d d 14 24 34 44 54 64 74 d d d d d d d 15 25 35 45 55 65 75 d d d d d d d 16 26 36 46 56 66 76 d d d d d d d 17 27 37 47 57 67 77 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 第二步，以各顶点的载荷（人口数）加权，求每一个顶点至其它各个顶点的 最短路径长度的加权和，可在Matlab环境下用矩阵运算求得： 定义各顶点的载荷矩阵： A = va ([ 1 ), va ( 2 ), va ( 3 ), va ( 4 ), va ( 5 ), va ( 6 ), va ( 7 )] = ]4.1.5.1.7.2,3[ S = vS ([ 1 ), vS ( 2 ), vS ( 3 ), vS ( 4 ), vS ( 5 ), vS ( 6 ), vS ( 7 )] = AD * 142
    实习指导 --《计量地理学》（徐建华，华东师范大学） 输出结果： S vS ({min i i )} 第三步，判断 计算如下： 第一步： 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)
    实习指导 --《计量地理学》（徐建华，华东师范大学） 运行后输出S，即每一个顶点至其它各个顶点的最短路径长度的加权和： S = 122.3000 71.3000 69.5000 69.5000 108.5000 72.8000 95.3000 第三步： min(S) 运行后输出S的最小值： ans = 69.5000 判断：因为 vS ( 3 ) = vS ( ) = 4 vS ({min i )} = 5.69 i 。所以，v3和v4都是图9.2.3 的中位点。也就是说，中心邮局设在v3或v4都是可行的。 144
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料