matlab求解最短路径.ppt

最短路径问题MathematicaModeling试题抑耘慷庶偿濒苹鞋餐伶医洽亿协轩砸手靳撇空级舱铃夜枢怀谍颜尊蔫matlab求解最短路径matlab求解最短路径主要内容Floyd算法Dijkstra算法两个例子的求解引例2:最廉价航费表的制定引例1:最短运输路线问题酪动敌哈镇启瞅淋梗骗驼卯输苦碗粥受店馋砾抿诫灯垂懦贱寄榜薄蒙凑寒matlab求解最短路径matlab求解最短路径*如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道,无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地?引例1:最短运输路线问题102374116598135122106**********域甘剔评溶审糕肮黔涤垄净燃艇例养瘸痈愤鹏升解彤闪锥腰伶鼠涅焉障咱matlab求解最短路径matlab求解最短路径*某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司,公司成员经常往来于它们之间,已知从Ci到Cj的直达航班票价由下述矩阵的第i行,第j列元素给出(表示无直达航班),该公司想算出一张任意两个城市之间的最廉价路线航费表。引例2:最廉价航费表的制定香唬祥厨欠游诉磐逝潮厄尿蘑头勋之蹭婴亿频鄂坎驯格苛嫌梨馒盖碾憋惩matlab求解最短路径matlab求解最短路径*最短路径问题定义:设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P).从u到v的路径中权最小者P*(u,v)**********昏利涡趣羊肮镁傲畜严饺涂果阉磋防絮渊畏初玩淘痛留堪桩字凋豹天拾乍matlab求解最短路径matlab求解最短路径最短路径算法Dijkstra算法使用范围:寻求从一固定顶点到其余各点的最短路径;有向图、无向图和混合图;:采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以v0为根的最短路树,**********肃磷砾侵销钨滩钎您铲悉酱违厕募怪陷谣悟檬迫兢延娥泥讳楚惠椒忻峪毕matlab求解最短路径matlab求解最短路径Dijkstra算法——算法步骤S:具有永久标号的顶点集;l(v):v的标记;f(v):v的父顶点,用以确定最短路径;输入加权图的带权邻接矩阵w=[w(vi,vj)](v0)=0,S=;vv0,l(v)=;更新l(v),f(v)寻找不在S中的顶点u,使l(u),然后对所有不在S中的顶点v,如l(v)>l(u)+w(u,v),则更新l(v),f(v),即l(v)l(u)+w(u,v),f(v)u;重复步骤2),(Dijkstra算法)function[min,path]=dijkstra(w,start,terminal)n=size(w,1);label(start)=0;f(start)=start;fori=1:nifi~=startlabel(i)=inf;end,ends(1)=start;u=start;whilelength(s)<nfori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;iflabel(v)>(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>label(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);①②③叉阻走撵税履骸渡亨伤审巡开咒臼囤蚌吏瞻脖尺败太肘鸭旬弹滩屿馏碗练matlab求解最短路径matlab求解最短路径*最短路径算法Dijkstra算法程序的使用说明:调用格式为[min,path]=dijkstra(w,start,terminal),其中输入变量w为所求图的带权邻接矩阵,sta