最短路径问题-数学建模说课材料.ppt

《最短路径问题-数学建模说课材料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路径问题-数学建模如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？引例1：最短运输路线问题102374116598135122106158879932272某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司，公司成员经常往来于它们之间，已知从Ci到Cj的直达航班票价由下述矩阵的第i行，第j列元素给出（表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。引例2：最廉价航费表的制定3最短路径问题定义：设P(u,v)是加权图G

2、中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P).从u到v的路径中权最小者P*(u,v)称为u到v的最短路径.102374116598135122106158879932274最短路径算法Dijkstra算法使用范围:寻求从一固定顶点到其余各点的最短路径;有向图、无向图和混合图;权非负.算法思路：采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径.102374116598135122106158879932275Dijkstra算法——算法步骤S:具有永久标号的顶点集;l(v):v的标记;f(v):v的

3、父顶点,用以确定最短路径;输入加权图的带权邻接矩阵w=[w(vi,vj)]nxm.初始化令l(v0)=0,S=;vv0,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中为止.6MATLAB程序（Dijkstra算法）function[min,path]=dijkstra(w,start,terminal)n=size(w,1);label(start)=0;f(start)

4、=start;fori=1:nifi~=startlabel(i)=inf;end,ends(1)=start;u=start;whilelength(s)(label(u)+w(u,v))label(v)=(label(u)+w(u,v));f(v)=u;end,end,endv1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;ifk>labe

5、l(v)k=label(v);v1=v;end,end,ends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1;whilepath(i)~=startpath(i+1)=f(path(i));i=i+1;endpath(i)=start;L=length(path);path=path(L:-1:1);①②③7最短路径算法Dijkstra算法程序的使用说明：调用格式为[min,path]=dijkstra(w,start,terminal),其中输入变量w为所求图的带权邻接矩阵，start,terminal分别

6、为路径的起点和终点的号码。返回start到terminal的最短路径path及其长度min.注意：顶点的编号从1开始连续编号。8最短路径算法Floyd算法使用范围:求每对顶点的最短路径;有向图、无向图和混合图;算法思想:直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2),…,D(n),D(n)是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径.102374116598135122106158879932279Floyd算法——算法步骤d(i,j):i到j的距离;path(i,j):i到j的路径上i的后继点;输入带权邻接矩阵a(i,j).1）赋初值对所有i

7、,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)