文档介绍：两个指定顶点之间的最短路径
问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,找一条最短铁路线。
以各城镇为图的顶点,两城镇间的直通铁路为图相应两顶点间的边,得图。对的每一边,赋以一个实数—直通铁路的长度,称为的权,得到赋权图。的子图的权是指子图的各边的权和。问题就是求赋权图中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路,它的权叫做间的距离,亦记作。
求最短路已有成熟的算法:迪克斯特拉(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:le