Matlab最短路径算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最短,路径问题,Mathematica Modeling,参考书：,1.,傅鹂 龚劬 刘琼荪 何中市,数学实验,科学出版社,2.,张绍民 李淑华,数据结构教程,C,语言版,中国电力出版社,主讲：重庆大学 龚 劬,1,主要内容,Floyd,算法,Dijkstra,算法,两个例子的求解,引例,2,：最廉价航费表的制定,引例,1,：最短运输路线问题,2,如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从,1,号顶点运往,11,号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？,引例,1,：,最短运输路线问题,10,2,3,7,4,11,6,5,9,8,1,3,5,12,2,10,6,1,5,8,8,7,9,9,3,2,2,7,3,某公司在六个城市,C,1,C,2,C,3,C,4,C,5,C,6,都有分公司，公司成员经常往来于它们之间，已知从,Ci,到,C,j,的直达航班票价由下述矩阵的第,i,行，第,j,列元素给出（,表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。,引例,2,：,最廉价航费表的制定,4,最短路径问题,定义：设,P(u,v),是加权图,G,中从,u,到,v,的路径,则该路径上的边权之和称为该路径的权,记为,w(P).,从,u,到,v,的路径中权最小者,P*(u,v),称为,u,到,v,的最短路径,.,10,2,3,7,4,11,6,5,9,8,1,3,5,12,2,10,6,1,5,8,8,7,9,9,3,2,2,7,5,最短路径算法,Dijkstra,算法,使用范围,:,寻求从一固定顶点到其余各点的最短路径,;,有向图、无向图和混合图,;,权非负,.,算法思路：,采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以,v,0,为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径,.,10,2,3,7,4,11,6,5,9,8,1,3,5,12,2,10,6,1,5,8,8,7,9,9,3,2,2,7,6,Dijkstra,算法,算法步骤,S:,具有永久标号的顶点集,;,l(v):v,的标记,;f(v):v,的父顶点,用以确定最短路径,;,输入加权图的带权邻接矩阵,w=,w(v,i,v,j,),nxm,.,初始化 令,l(v,0,)=0,S=,;vv,0,l(v)=;,更新,l(v),f(v),寻找不在,S,中的顶点,u,使,l(u),为最小,.,把,u,加入到,S,中,然后对所有不在,S,中的顶点,v,如,l(v)l(u)+w(u,v),则更新,l(v),f(v),即,l(v),l(u)+w(u,v),f(v)u;,重复步骤,2),直到所有顶点都在,S,中为止,.,7,MATLAB,程序（,Dijkstra,算法）,function min,path=,dijkstra(w,start,terminal,),n=size(w,1);label(start)=0;f(start)=start;,for i=1:n,if i=start,label(i)=,inf,;,end,end,s(1)=start;u=start;,while length(s)(label(u)+w(u,v),label(v)=(label(u)+w(u,v);f(v)=u;,end,end,end,v1=0;,k=,inf,;,for i=1:n,ins=0;,for j=1:length(s),if i=s(j),ins=1;,end,end,if ins=0,v=i;,if klabel(v),k=label(v);v1=v;,end,end,end,s(length(s)+1)=v1;,u=v1;,end,min=label(terminal);path(1)=terminal;,i=1;,while path(i)=start,path(i+1)=f(path(i);,i=i+1;,end,path(i)=start;,L=length(path);,path=path(L:-1:1);,8,最短路径算法,Dijkstra,算法程序的使用说明：,调用格式为,min,path=,dijkstra(w,start,terminal,),其中输入变量,w,为所求图的带权邻接矩阵，,start,terminal,分别为路径的起点和终点的号码。,返回,start,到,terminal,的最短路径,path,及其长度,min.,注意：顶点的编号从,1,开始连续编号。,9,最短路径算法,Floyd,算法,使用范围,:,求每对顶点的最短路径,;,有向图、无向图和混合图,;,算法思想,:,直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出,n,个矩阵,D(1),D(2),D(n),D(n),是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径,.,10,2,3,7,4,11,6,5,9,8,1,3,5,12,2,10,6,1,5,8,8,7,9,9,3,2,2,7,10,Floyd,算法,算法步骤,d(i,j):i,到,j,的距离,;,path(i,j):i,到,j,的路径上,i,的后继点,;,输入带权邻接矩阵,a(i,j).,1,）,赋初值,对所有,i,j,d(i,j),a(i,j),path(i,j)j,k=l.,2,）,更新,d(i,j),path(i,j),对所有,i,j,若,d(i,k)+d(k,j)d(i,j),则,d(i,j)d(i,k)+d(k,j),path(i,j)path(i,k),k k+1,3,）,重复,2),直到,k=n+1,11,MATLAB,程序（,Floyd,算法,）,function D,path,min1,path1=,floyd(a,start,terminal,),D=a;n=size(D,1);path=zeros(n,n);,for i=1:n,for j=1:n,if D(i,j)=,inf,path(i,j)=j;,end,end,end,for k=1:n,for i=1:n,for j=1:n,if D(i,k)+D(k,j)D(i,j),D(i,j)=D(i,k)+D(k,j);,path(i,j)=path(i,k);,end,end,end,end,if,nargin,=3,min1=D(start,terminal);,m(1)=start;,i=1;,path1=;,while path(m(i),terminal)=terminal,k=i+1;,m(k)=path(m(i),terminal);,i=i+1;,end,m(i+1)=terminal;,path1=m;,end,12,最短路径算法,Floyd,算法程序的使用说明：,1.D,path=,floyd(a,),返回矩阵,D,path,。,其中,a,是所求图的带权邻接矩阵，,D(i,j),表示,i,到,j,的最短距离,;path(i,j),表示,i,与,j,之间的最短路径上顶点,i,的后继点,.,2.D,path,min1,path1=,floyd(a,i,j,),返回矩阵,D,path;,并返回,i,与,j,之间的最短距离,min1,和最短路径,path1.,13,edge=2,3,1,3,3,5,4,4,1,7,6,6,5,5,11,1,8,6,9,10,8,9,9,10;.,3,4,2,7,5,3,5,11,7,6,7,5,6,11,5,8,1,9,5,11,9,8,10,9;.,3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7,2,9,9,2,2;,n=11;weight=,inf,*ones(n,n);,for i=1:n,weight(i,i)=0;,end,for i=1:size(edge,2),weight(edge(1,i),edge(2,i)=edge(3,i);,end,dis,path=,dijkstra(weight,1,11),引例,1,的,Matlab,求解,10,2,3,7,4,11,6,5,9,8,1,3,5,12,2,10,6,1,5,8,8,7,9,9,3,2,2,7,14,运行上页程序输出：,dis,=,21,path=,1 8 9 10 11,因此顶点,1,到顶点,11,的最短路径为,18 9 10 11,其长度为,21,。,引例,1,的求解,15,建立脚本,m,文件如下：,a=0,50,inf,40,25,10;50,0,15,20,inf,25;inf,15,0,10,20,inf;,40,20,10,0,10,25;25,inf,20,10,0,55;10,25,inf,25,55,0;,D,path=,floyd(a,),运行便可输出结果。,引例,2,的,Matlab,求解,16,运行输出结果：,D=,0 35 45 35 25 10,35 0 15 20 30 25,45 15 0 10 20 35,35 20 10 0 10 25,25 30 20 10 0 35,10 25 35 25 35 0,path=,1 6 5 5 5 6,6 2 3 4 4 6,5 2 3 4 5 4,5 2 3 4 5 6,1 4 3 4 5 1,1 2 4 4 1 6,D,便是最廉价的航费表，要求飞行路线，由,path,矩阵可以得到，比如,2,到,5,的路线：,path(2,5)=4,path(4,5)=5,因此，应为,24 5,17,