1 / 17
文档名称:

matlab最短路径算法.ppt

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

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

分享

预览

matlab最短路径算法.ppt

上传人:vqjyga55 2019/4/12 文件大小:108 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算法程序的使用说明:调用格

最近更新

针织用纱质量浅析 3页

采用精密距离测量在基坑平面位移中的应用 3页

《山中访友》教学设计 32页

连铸圆坯结晶器锥度优化设计研究 3页

辐照前处理木质纤维素的研究进展 3页

超声波淬火工艺在40Cr阶梯轴淬火中的应用 3页

论XBRL分类标准扩展——以石油天然气行业为例.. 3页

西非地区路网规划特点及公路建设发展研究 3页

行政事业单位内控测试评价、缺陷与优化探析 4页

表演动作猜成语素材 111页

苏54区块盒 8段储层气水分布特征及识别方法研.. 3页

2025年农村住房租赁市场租赁合同租赁权转让合.. 8页

职业企业家行为失范机理分析及其约束机制研究.. 3页

绩效考核在医院人力资源管理中的应用研究 3页

蒸发和降水的观测 57页

第六届粤港澳大湾区“粤菜师傅”技能大赛中式.. 13页

福建省旅游业发展前景SWOT分析 3页

硬质合金自动切菜机刀具设计及工艺优化 4页

石油销售企业竞争力的增强方式分析与研究 3页

苏霍姆林斯基给教师的100条建议之 9页

2025年鼓励孩子多读书的金句 7页

2025年鸡年农历九月宝宝取名技巧 4页

2025年高考选科选物理一定要选化学吗 4页

2025年高考毕业串场词 20页

苏卫单招校测2025试卷 9页

《黄河颂》33694省公开课一等奖全国示范课微课.. 29页

部编版九年级语文上册必背古诗文 8页

消毒小车策划书 4页

3D打印技术与虚拟现实的融合 26页

党建调研提纲 2页