资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,两种经典最短路径问题_Dijkstra和Floyd算法,两种经典最短路径问题_Dijkstra和Floyd算法,如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从,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,如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间,某公司在六个城市,C,1,C,2,C,3,C,4,C,5,C,6,都有分公司，公司成员经常往来于它们之间，已知从,Ci,到,C,j,的直达航班票价由下述矩阵的第,i行，第j列元素给出（,表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。,引例,2：,最廉价航费表的制定,某公司在六个城市C1,C2,C3,C4,C,最短路径问题,定义：设,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,最短路径问题定义：设P(u,v)是加权图G中从u到v的路径,最短路径算法,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,最短路径算法Dijkstra算法10237411659813,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中为止.,Dijkstra算法算法步骤S:具有永久标号的顶点集;,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);,MATLAB程序（Dijkstra算法）function,最短路径算法,Dijkstra,算法程序的使用说明：,调用格式为,min,path=dijkstra(w,start,terminal),其中输入变量,w为所求图的带权邻接矩阵，,start,terminal分别为路径的起点和终点的号码。,返回,start到terminal的最短路径path及其长度min.,注意：顶点的编号从1开始连续编号。,最短路径算法Dijkstra算法程序的使用说明：,最短路径算法,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,最短路径算法Floyd算法10237411659813512,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,Floyd算法算法步骤 d(i,j):i到j的,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,MATLAB程序（Floyd算法）function D,p,最短路径算法,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.,最短路径算法Floyd算法程序的使用说明：,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,edge=2,3,1,3,3,5,4,4,1,7,6,运行上页程序输出：,dis=,21,path=,1 8 9 10 11,因此顶点1到顶点11的最短路径为18 9 10 11,其长度为21。,引例,1的求解,运行上页程序输出：引例1的求解,建立脚本,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求解,建立脚本m文件如下：引例2的Matlab求解,运行输出结果：,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,运行输出结果：D=D便是最廉价的航费表，要求飞行路线，由,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力,
展开阅读全文