matlab_最短路径

《计量地理学》（徐建华，高等教育出版社，2005）配套实习指导 §19. 利用Matlab编程计算最短路径及中位点选址 1、最短路问题 两个指定顶点之间的最短路径。 例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图 的顶点，两城镇间的直通铁路为图 相应两顶点间的边，得图 。对 的每一边 ，赋以一个实数 —直通铁路的长度，称为 的权，得到赋权图 。 的子图的权是指子图的各边的权和。问题就是求赋权图 中指定的两个顶点 间的具最小权的轨。这条轨叫做 间的最短路，它的权叫做 间的距离，亦记作 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距 从近到远为顺序，依次求得 到 的各顶点的最短路和距离，直至 （或直至 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令 ，对 ，令 ， ， 。 (ii) 对每个 （ ），用 代替 。计算 ，把达到这个最小值的一个顶点记为 ，令 。 (iii). 若 ，停止；若 ，用 代替 ，转(ii)。 算法结束时，从 到各顶点 的距离由 的最后一次的标号 给出。在 进入 之前的标号 叫T标号， 进入 时的标号 叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时， 至各项点的最短路也在图上标示出来了。 例1： 某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。 用矩阵 （ 为顶点个数）存放各边权的邻接矩阵，行向量 、 、 、 分别用来存放 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ； 存放始点到第 点最短通路中第 顶点前一顶点的序号； 存放由始点到第 点最短通路的值。 求第一个城市到其它城市的最短路径的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)