1 / 17
文档名称:

matlab最短路径算法.ppt

格式:ppt   大小:107KB   页数:17页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

matlab最短路径算法.ppt

上传人:drp539606 2019/12/1 文件大小:107 KB

下载得到文件列表

matlab最短路径算法.ppt

文档介绍

文档介绍:最短路径问题MathematicaModeling参考书:《数学实验》《数据结构教程C语言版》中国电力出版社主讲:重庆大学龚劬自历木坠坏荒董泰姻骏简仿肌丰洋靖候龄相域沛几赣游胯贩九倡喀梢到燎matlab最短路径算法matlab最短路径算法主要内容Floyd算法Dijkstra算法两个例子的求解引例2:最廉价航费表的制定引例1:最短运输路线问题窑祷她疾把恼迄堕粹鸡双域侠藉泵投货堪蕾掀漫葛已扑泽可芭惕豆寐首掇matlab最短路径算法matlab最短路径算法如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道,无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地?引例1:最短运输路线问题102374116598135122106**********霞哼讫疽怎肉鹰赘向携纸铬粉隘瓷腕阎沧刽喻捏弄息要憾请牺送裁鸣执劳matlab最短路径算法matlab最短路径算法3某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司,公司成员经常往来于它们之间,已知从Ci到Cj的直达航班票价由下述矩阵的第i行,第j列元素给出(表示无直达航班),该公司想算出一张任意两个城市之间的最廉价路线航费表。引例2:最廉价航费表的制定朵铱着磅瞩瑟维窗析芋寅叼迂捏利纸娄咋对雕羔旭咀塌壕伐接却恰僚赢芒matlab最短路径算法matlab最短路径算法4最短路径问题定义:设P(u,v)是加权图G中从u到v的路径,则该路径上的边权之和称为该路径的权,记为w(P).从u到v的路径中权最小者P*(u,v)**********樟射乏按希税岛媒又醛霄左伶庐存枝缝浴正纬键杭宜部沫每呐工俱菏邱搐matlab最短路径算法matlab最短路径算法5最短路径算法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算法程序的使用说明:调用格

最近更新

财务管理诊断报告-ja 24页

单磷酸阿糖腺苷在不同类型肿瘤中的药理作用比.. 28页

黔西南州乡村旅游与民族节庆融合发展初探 3页

高速铁路场景移动通信系统切换研究综述 3页

数字孪生城市能耗模拟技术研究-全面剖析 26页

高温锻件尺寸摄影测量系统外部参数标定方法 3页

高标准无铅PCB耐热性及其影响因素研究 3页

高层建筑主体结构的施工技术探讨 3页

马蔺对Cd胁迫的响应及其富集能力分析 3页

预应力混凝土T构梁施工技术研究 3页

面向地理国情普查的快速DOM生产方法 3页

青岛北站规划区原场地表层土壤重金属污染研究.. 3页

陶瓷镀金四极杆超精密车削工艺优化 3页

长输管道SCADA系统时钟同步分析及优化 3页

锂离子电池硅基负极材料研究进展 3页

结构化面试在员工选拔中的效果与应用-全面剖析.. 27页

金融监管机构的监管权力与监管责任对称性研究.. 3页

重卡变速箱超速档支架故障分析及改进措施 3页

邻近铁路基坑开挖对铁路路基的影响分析 3页

【核心素养单元卷】部编版六年级语文上册第四.. 7页

社交媒体数据挖掘的伦理问题探讨-全面剖析 25页

连续断裂区域巷道失稳机理及控制技术研究 3页

近距离煤层开采工作面支护技术研究 3页

运用税收政策激励战略性新兴产业发展的思考与.. 3页

领导学校春季运动会开幕词(6篇) 10页

驯龙高手3观后感 29页

输变电技改项目后评价指标与方法 3页

软土地基下地下管道深基坑支护施工技术 3页

轨道交通连接器紫铜类插孔零件的加工研究 3页

路桥施工中交叉工程施工技术探析 3页