《求最短路的算法程序》由会员分享，可在线阅读，更多相关《求最短路的算法程序（2页珍藏版）》请在金锄头文库上搜索。
1、求最短路已有成熟的算法：迪克斯特拉(Dijkstra)算法，其基本思想是按距u从近到远为顺序，依次求得u到G的各顶点的最短路和距离，直至v0 0 0(或直至G的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采 用了标号算法。下面是该算法。(i) 令 l(u )二 0，对 v 丰 u，令 /(v) = g， S 二u ， i = 0。0 0 0 0(ii) 对每个 v e S ( S = V S)，用iiimin/ (v), l (u) + w(uv)ueSi代替l(v)。计算minl(v)，把达到这个最小值的一个顶点记为u ，令 veS+1iS 二 S u u 。i+1ii+1(ii
2、i) .若i =IV I-1，停止；若i IV I-1，用 i +1 代替i，转(ii)。算法结束时，从u到各顶点v的距离由v的最后一次的标号l(v)给出。在v进 0入S之前的标号l(v)叫T标号，v进入S时的标号l(v)叫P标号。算法就是不断 ii修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获 得 P 标号所由来的边在图上标明，则算法结束时， u 至各项点的最短路也在图 0上标示出来了。例某公司在六个城市c ,c ,c中有分公司，从c到c的直接航程票价126ij记在下述矩阵的(i,j)位置上。(表示无直接航路)，请帮助该公司设计一张城市c到其它城市间的票价最便宜的路线图
3、。1050g4025105001520g25g1501020g4020100102525g20100551025g25550用矩阵a( n为顶点个数)存放各边权的邻接矩阵，行向量pb、indexnxn1index 、 d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路 2的值。其中分量pb(i)二1当第i顶点已标号0当第i顶点未标号index2(i)存放始点到第i点最短通路中第i顶点前一顶点的序号;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;index1=1;index2=ones(1,length(a); d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);endindex2(temp)=index;endd, index1, index2
