图论中最短路问题的matlab程序实现[1]

《图论中最短路问题的matlab程序实现[1]》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、安庆师范学院学报(自然科学版)2007年2007年2月安庆师范学院学报(自然科学版)Feb.2007第13卷第1期JournalofAnqingTeachersCollege(NaturalScienceEdition)Vol.13No.1图论中最短路问题的MATLAB程序实现管志忠1,22,刘永明(1.池州职业技术学院,安徽池州24700;2.华东师范大学数学系,上海200062)摘要:解决图论中最短路问题的最好方法--“Dijstra算法”,通过解析实例模型,对模型算法进行描述、拓展,并给出了求最短路以及求

2、最短路长的MATLAB程序,此程序具有通用性。关键词:最短路问题;Dijkstra算法;MATLAB程序;最短路长中图分类号:O157.5文献标识码:A文章编号:1007-4260(2007)01-0026-041问题的提出设G=(V,E)为连通图,顶点集为{1,2,3,⋯n},图中各边(i,j)有非负权cij(当(i,j)不是边时,权等于inf;当(i,j)是有向边时,cji与cij可以不相等),求一条道路使它是从顶点1到顶点n的所有道路中总权数最小的路,这就是图论中的最短路问题[1]。解决这个问题至今公认最

3、好的方法是1959年提出Di-jkstra算法,它用于计算一个点s到其他所有点的最短路。此算法基本原理是:若某条路是最短路,这条路上的任意一段路也是连接这段路两个端点的最短路[1,2]。2算法描述[3,4]第一步将点s标上永久性标记P(s)=0,表示从开始点s到达点s的最短距离是零。第二步将其余的顶点标上T标记,T记号是试探性标记,点j的T标记T(j)分两部分,T(j)=T1(j)(T2(j)),第一部分T1(j)为从开始点s经过带P标记的点到达j点的最短路的权和,括号中T2(j)为第二部分,是这最短路中j点的

4、前一点(如有多条最短路,则T2(j)可能有多值)。不能经过带P标记的点到达的点的T1值是无穷大(用inf表示),T2是空集。第三步若这些带有T标记中权和数T1最小的点是k,则点k是带P标记的点外与开始点s最近的点。把点k的T标记改为P标记,如果权和数最小的点有多个,则把它们都改为P标记。若点n不是P标记,转第二步(对带有T标记的点重新标记,直至点n为P标记为止)。第四步追寻最短路,从终点n开始逆向逐次求最短路经过的点权和为P(n).从算法直接可见所得到的路是最短路。上述算法更具体的步骤如下:不妨设开始点的标号是

5、1。⑴设N=0,P(1)=0,其余各点都是T标记,T1值为无穷大,T2值为空集。⑵若vi点为刚成为P标记的(一个或几个)点,将所有与这些vi相邻的带有T标记的点vj的T标记的值改为;若T1(vj,N+1)=P(vi)+cij,则T2(vj,N+1)=vi,若T1(vj,N+1)=T1(vj,N),则T2(vj,N+1)=T2(vj,N),(因此T2可能是多值的)。⑶比较所有具有T标记的点,把其中T1值最小者的点vk的T标记改为P标记,P(vk)=minT1(vj,N+1);当存在两个以上的最小者时,可同时将它们

6、改为P标记;若点vk=n则转(4),否则将N加上1,用vk代vi转回(2)。⑷追寻最短路,从终点n开始逆向逐次求最短路经过的点(可能不止一条最短路),权和为P(n)。3算法拓展与MATLAB程序实现求n个顶点的连通图G上任意两点间的最短路长的算法(它是下面要讲的Floyd(1962)算法的改收稿日期:2006-09-14作者简介:管志忠(1965-),男,安徽池州人,华东师范大学硕士,池州职业技术学院副教授,专业方向:应用数学。第1期管志忠,刘永明:图论中最短路问题的MATLAB程序实现·27·进,但它只适用于

7、非负权的最短路问题)。设lij为顶点i到j的距离,令图G的权矩阵,为算法基本步骤为[5]:⑴(0)输入权矩阵D.⑵计算,其中表示从点i到点j的距离,或者经过某一个中间点到达j点的最短路。⑶若,则就是i到j的最短路长,不然,取=D,转(2)。其中第(2)步最多执行max1=floor(log(2*n-3)/log(2))次。其原理是:第(2)步得到的矩阵的元素dij表示从i点到j点的距离,或i点能经过另一点k到达j点的距离中的最小值。因此每执行一次步骤(2)所得到的矩阵D相当于另一个图的矩阵,这个图的构造是:当d

8、ij的值小于原矩阵的值时,将原图上将i,j点之间加上一条权为dij的边,若原来有边,则改变它的权为dij.设i,j点间有一条最短路,这最短路有m个顶点,不妨记这些顶点为i,i+1,i+2,⋯,i+m-1=j,经过一次(2)的步骤时,求得(i,i+2),(i+2,i+4),⋯⋯的长度,再经过一次(2)的步骤时,得到(i,i+4),(i+4,i+8),⋯⋯的长度,⋯⋯.因为当2^k>=m-