


下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
最短路线的最短化
1式海斯算法与德国助力“负权”图自1960年以来,研究最相关的问题一直成果。其中,荷兰著名计算机专家e.w.dijkas首次提出了赋权图(wij0)的有效算法。这一算法可以解决两个点之间的最短距离,或者图g中的点1到其他点之间的最短距离。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在(wij≥0)的情况下选择Dijkstra算法。定义1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。定义2若图G=G(V,E)是赋权图且W(e)≥0,e∈E(G),若u是vi到vj的路W(u)的权,则称W(u)为u的长,长最小的vi到vj的路W(u)称为最短路。若要找出从v1到vn的通路u,使全长最短,即minW(u)=∑eij∈uW(e)minW(u)=∑eij∈uW(e)。2vjvk的求取vd在诸多算法中(wij≥0)最经典的算法当属Dijkstra算法,该算法的基本思想是动态规划最优原理,即最短路线上任意两点间的路线也是最短。因此,若vi到vj的最短路线经过vk,则vi到vk以及vk到vj的部分都是相应的最短路线。基本步骤:令s={v1},i=1,ˉs={v2,v3‚⋯‚vn}并令{W(v1)=0Τ(vj)=∞,vj∈ˉs①对vj∈ˉs,求min{T(vj),W(vi)+wij}=T(vj)。②求minvj∈ˉs{Τ(vj)}得T(vk),使Τ(vk)=minvj∈ˉs{Τ(vj)}令W(vk)=T(vk)③若vk=vn则已找到v1到vn的最短路距离W(vk),否则令i=k从ˉs中删去vi转①这样经过有限次迭代则可以求出v1到vn的最短路线,可以用一个流程图来表示:第一步先取W(v1)=0意即v1到v1的距离为0,而T(vj)是对W(vj)所赋的初值。第二步利用W(v1)已知,根据min{T(vj),W(vi)+wij}对T(vj)进行修正。第三步对所有修正后的T(vj)求出其最小者T(vk)。其对应的点vk是v1所能一步到达的点vj中最近的一个,由于所有W(u)≥0。因此任何从其它点vj中转而到达vk的通路上的距离都大于v1直接到vk的距离T(vk),因此T(vk)就是v1到vk的最短距离,所以在算法中令W(vk)=T(vk)并从ˉs中删去vk,若k=n则W(vk)=W(vn)就是v1到vn的最短路线,计算结束。否则令vi=vk回到第二步,继续运算,直到k=n为止。这样每一次迭代,得到v1到一点vk的最短距离,重复上述过程直到vk=vn。3vtvj计算设6个城市v1,v2,…,v6之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市v1,那么从v1到v6应选择哪一路径使你的费用最省。解:首先设每百公里所用费用相同,求v1到v6的费用最少,既求v1到v6的最短路线。为了方便计算,先作出该网络的距离矩阵,如下:L=[v1v2v3v4v5v6v1052∞∞∞v250159∞v3210810∞v4∞58025v5∞910202v6∞∞∞520](0)设W(v1)=0,Τ(v)=∞,vj∈ˉs={v2,v3,v4,v5,v6}‚(1)第一次迭代①计算T(vj),j=2,3,4,5,6如下T(v2)=min{T(v2),W(v1)+w12}=min{∞,0+5}=5T(v3)=min{T(v3),W(v1)+w13}=min{∞,0+2}=2T(v4)=min{T(v4),W(v1)+w14}=min{∞,0+∞}=∞T(v5)=∞,T(v6)=∞②取minvj∈ˉs{Τ(vj)}=2=Τ(v3),令W(v3)=T(v3)=2③由于k=3≠(n=6),令ˉs={v2,v4,v5,v6},i=3转(1)第二次迭代:①算T(vj),j=2,4,5,6如下T(v2)=min{T(v2),W(v3)+w23}=min{5,2+1}=3T(v4)=min{T(v4),W(v3)+w34}=min{8,2+8}=8T(v5)=min{T(v5),W(v3)+w35}=min{10,2+10}=10T(v6)=min{T(v6),W(v3)+w36}=min{∞,2+∞}=∞②取minvj∈ˉs{Τ(vj)}=3=Τ(v2)令W(v2)=T(v2)=3③由于k=2≠(n=6),令ˉs={v4,v5,v6}i=2转(1)第三次迭代:①算T(vj),j=4,5,6如下Τ(v4)=min{Τ(v4),W(v2)+w24}=min{8,3+5}=8Τ(v5)=min{Τ(v5),W(v2)+w25}=min{10,3+9}=10Τ(v6)=∞②minvj∈ˉs{Τ(vj)}=8=Τ(v4)‚W(v4)=Τ(v4)=8③由于k=4≠(n=6),令ˉs={v5,v6}i=4转(1)第四次迭代:①算T(vj),j=5,6如下T(v5)=min{T(v5),W(v4)+w45}=min{10,2+8}=10T(v6)=min{T(v6),W(v4)+w46}=min{∞,8+5}=13②取minvj∈ˉs{Τ(vj)}=10=Τ(v5),令W(v5)=T(v5)=10③由于k=5≠(n=6),令ˉs={v6}转(1)第五次迭代:①算T(vj),j=6如下T(v6)=min{T(v
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2.2社会主义制度在中国的确立 课件 统编版高中思想政治必修1中国特色社会主义
- 纳税评估工作总结十篇
- 老年日常康复护理课件
- 老年护理课件题目
- 老年人慢性病课件
- 老年中医课件制作
- 通信设备车间使用权及技术转让合同模板
- 保险理赔责任限制条件合同
- 大学国家安全教育考试试题及答案
- 辅警培训课件
- 信息系统的使用与维护管理制度
- 全国中小学生学籍信息管理系统用户操作手册(学校级)
- 2025年北京市第一次普通高中学业水平合格性考试仿真模拟物理试卷01(解析版)
- 稽留流产治疗
- 农村基础设施建设小微权力清单流程
- 雪亮工程可行性研究报告
- 小学班会-小学生主题班会版期末颁奖班会-蔬菜篇(课件)(共23张课件)
- 肝包虫手术麻醉
- 《银行礼仪培训方案》课件
- 床上用品采购投标方案(技术方案)
- 电力系统继电保护课后习题解析(第二版)-张保会-尹项根主编
评论
0/150
提交评论