《最短路径的Dijkstra算法及Matlab程序.pdf》由会员分享，可在线阅读，更多相关《最短路径的Dijkstra算法及Matlab程序.pdf（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 word 文档 可自由复制编辑 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数)(ew直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点00,vu间的具最小权的轨。这条轨叫做00,vu间的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的
2、各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i)令0)(0ul，对0uv，令)(vl，00uS，0i。(ii)对每个iSv（iiSVS），用)()(),(minuvwulvliSu 代替)(vl。计算)(minvliSv，把达到这个最小值的一个顶点记为1iu，令11iiiuSS。(iii).若1|Vi，停止；若1|Vi，用1i代替i，转(ii)。算法结束时，从0u到各顶点v的距离由v的最后一次的标号)(vl给出。在v进入iS之前的标号)(vl叫 T 标号，v进入iS时的标号)(vl叫 P 标号。算法就是不断修
3、改各项点的 T标号，直至获得 P 标号。若在算法运行过程中，将每一顶点获得 P 标号所由来的边在图上标明，则算法结束时，0u至各项点的最短路也在图上标示出来了。例 1 某公司在六个城市126,c ccL中有分公司，从ic到jc的直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航路），请帮助该公司设计一张城市1c到其它城市间的票价最便宜的路线图。055252510550102025251001020402010015252015050102540500 word 文档 可自由复制编辑 解 用矩阵nna（n为顶点个数）存放各边权的邻接矩阵，行向量pb、1index、2index、d分别用来
4、存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 顶点未标号当第顶点已标号当第iiipb01)(；)(2iindex 存放始点到第i点最短通路中第i顶点前一顶点的序号；)(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;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);end index2(temp)=index;end d,index1,index2