![最短路径问题的算法分析及建模案例_第1页](http://file4.renrendoc.com/view14/M09/35/13/wKhkGWZeeFSAeyZ-AABBZx7omjk853.jpg)
![最短路径问题的算法分析及建模案例_第2页](http://file4.renrendoc.com/view14/M09/35/13/wKhkGWZeeFSAeyZ-AABBZx7omjk8532.jpg)
![最短路径问题的算法分析及建模案例_第3页](http://file4.renrendoc.com/view14/M09/35/13/wKhkGWZeeFSAeyZ-AABBZx7omjk8533.jpg)
![最短路径问题的算法分析及建模案例_第4页](http://file4.renrendoc.com/view14/M09/35/13/wKhkGWZeeFSAeyZ-AABBZx7omjk8534.jpg)
![最短路径问题的算法分析及建模案例_第5页](http://file4.renrendoc.com/view14/M09/35/13/wKhkGWZeeFSAeyZ-AABBZx7omjk8535.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
最短路径问题的算法分析及建模案例最短路径问题的算法分析及建模案例TOC\o"1-3"\h\u12477一.摘要 38159二.网络最短路径问题的基础知识 58582.1有向图 719722.2连通性 错误!未定义书签。271242.3割集 错误!未定义书签。169532.4最短路问题 85517三.最短路径的算法研究 错误!未定义书签。152563.1最短路问题的提出 930853.2Bellman最短路方程 错误!未定义书签。109753.3Bellman-Ford算法的基本思想 错误!未定义书签。220253.4Bellman-Ford算法的步骤 错误!未定义书签。217903.5实例 错误!未定义书签。204383.6Bellman-FORD算法的建模应用举例 错误!未定义书签。191263.7Dijkstra算法的基本思想 9246233.8Dijkstra算法的理论依据 9307003.9Dijkstra算法的计算步骤 9104763.10Dijstre算法的建模应用举例 10274473.11两种算法的分析 错误!未定义书签。109151.Diklstra算法和Bellman-Ford算法思想有很大的区别 错误!未定义书签。1767Bellman-Ford算法在求解过程中,每次循环都要修改所有顶点的权值,也就是说源点到各顶点最短路径长度一直要到Bellman-Ford算法结束才确定下来。 错误!未定义书签。230862.Diklstra算法和Bellman-Ford算法的限制 错误!未定义书签。166613.Bellman-Ford算法的另外一种理解 错误!未定义书签。244144.Bellman-Ford算法的改进 错误!未定义书签。摘要近年来计算机发展迅猛,图论的研究也得到了很大程度的发展,而最短路径问题一直是图论中的一个典型问题,它已应用在地理信息科学,计算机科学等诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的一个典型例子。由于最短路径问题在各方面广泛应用,以及研究人员对最短路径的深入研究,使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最短路径问题的算法以及各算法之间的比较,最后将这些算法再应用于实际问题图11.1图图G是一个(无向)图,其中有序二元组(V,E),V={,,...}是顶点集,E={}是集,是一个无序二元组{,}它表示该边连接的是顶点,。图1就是一个图。注释:图形的大小,位置,形状是无关紧要的。若={,}则称连接和;点和称为的顶点,和是邻接的顶点;如果两条边有公共的一个顶点,则称这两边是邻接的。1.2无环图定义:没有环的图称之为无环图。1.3简单图定义:没有环且没有重边的图称之为简单图。设G=(V,E)是一个简单图,则有|E|不大于|V|(|V|-1)/21.4完全图定义:若上式的等号成立那么该图中每对顶点恰好有一条边相连,则称该图为完全图。1.5有向图定义:一个有向图G是一个有序二元组(V,A),V={,,...,}是顶点集,A={}称为G的弧集,为有序二元组。称为连向的弧,为的出弧,的入弧;称为的得尾,称为aij的头;称为的前继,称为的后继。图2就是一个有向图。图21.6环定义:头尾重合的弧称为环。1.7简单有向图定义:没有环和重弧的有向图称为简单有向图。1.8完全有向图定义:设G=(V,E)是一个简单有向图,则|A|不大于|V|(|V|-1),若等号成立则称这样的图为完全有向图。1.9途径,迹,路定义:设图G=(V,E),若它的某些顶点与边可以排成一个非空的有限交错序列(,,,...,),这里该途径中边互不相同,则称为迹;如果顶点互不相同,则称之为路。显然路必为迹,但反之不一定成立。1.10连通图定义:图G中如果存在一条从顶点到的途径,则称和是连通的。如果图G中任何两个顶点都是连通的,则称G是连通图。1.11有向途径定义:设有一个有向图G=(V,A),G中某些顶点与弧组成的非空有限序列(,,,,...,,)这里,...,V,A,且=(,),则称它为从到的有向途径。类似的可定义有向迹,有向路,有向闭途径,有向闭迹,有向回路(圈)等。当G时简单有向图时,从到的一条有向途径可简记为(,...,)。二最短路问题定义:所谓最短路径是指如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一跳有向路径使得沿这条路径上各弧的权值总和最小。2.1最短路问题的提出某旅客要从杭州乘飞机前往奥地利的萨尔斯堡,因为他害怕乘坐飞机,因此要选择一条航线,使得在空中飞行的时间尽可能的少。如何选择航线以达到要求。为此构造一个无向网络总可以化成有向网络。设G=(V,A,w)是一个有向网络,p为G中一条有向路,称w(P)=为路径p的路长。现找网络中一条从指定顶点vi到另一个指定顶点vj的最短有向路径。三最短路径算法研究3.1Dijkstra算法3.11Dijkstra算法的基本思想对网络中每个顶点赋一个标号,用来记录从顶点到该顶点的最短路的长度(称为永久标号)或最短长度的上界(称为临时标号)。算法开始时,只有顶点被赋予永久标号=0,其他顶点赋予临时标号。一般的,算法在被临时标号的顶点中寻找一个顶点,其临时标号最小,然后将赋予永久标号,并且对其余临时标号的顶点vj按照方式修正其标号。算法在所有顶点被赋予永久标号时结束。3.12Dijkstra算法的理论依据对于S中任意一顶点,其永久标号都是从顶点到该顶点的最短路的长度。对于R中任意一顶点,其临时标号都是从顶点出发,只经过S中顶点到达该顶点的最短路的长度。3.13Dijkstra算法的计算步骤最短路径问题是指在一个赋予权值的图的两个指定节点和v之间找出一条具有最小权值的路。Dijkstra算法是一个解最短路径问题的算法,这个算法不仅可以找到最短的(,v),路径而且可以给出从到图中所有节点的最短路径,基本步骤如下:设=0,对所有节点来说,设=,并且将标号为0,→t,d为和w之间的权值(距离)。按照每个没有标号的节点w计算,,表示节点t到节点w之间的权值。如果标号被修改了说明在当前得到的到w的最优路径上t和w相邻,用记录下来在所有中选择一个最小的即,w未标号。将s标号为/,表示节点到s的最优路径的长度且与s相邻。如果重点v已经标号,则停止。得到一条从到v的最优路径。否则s→t,反向。按照上述步骤继续计算。3.14Dijstre算法的建模应用举例某城市要在该城市所辖的8个区中的区建立一个取水点,如图所示的是这8个区之间的分布以及相邻各区的距离。现要从区向其他各区运水,求出区到其他各区的最短路径。先写出带权邻接矩阵:W=因为G是无向图,所以W是对称矩阵。迭代次数1020218328104831058610126710127912812最后标记L(v)021736912Z(v)因此得到最短路径为:迭代次数最后标记L(v)021736912Z(v)由上表可得到到各点的最短路径为:;;,,;;;,,;,。上述Dijkstra算法的MATLAB代码:w=[0218infinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);%赋初值%fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1;whilek<n%更新l(v)和z(v)%fori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendl,z%求v*L1=1;fori=1:nforj=1:kifi~=s(j)l1(i)=l1(i);elsel1(i)=inf;endendendlv=inf;fori=1:nifl1(i)<lvlv=l1(i);v=i;endendlv,vs(k+1)=vk=k+1u=s(k)endl,z3.2FLOYD算法3.21FLOYD算法的基本思想直接在图的带权邻接矩阵中使用插入顶点的方法依次构造出n个矩阵,...,,使得最终得到的矩阵成为图的距离矩阵,并且同时求出插入的点的矩阵以便于得到两点间的最短路径。3.22FLOYD算法原理(1)FLOYD算法求路径矩阵的方法:在建立距离矩阵的同时可建立路径矩阵R。每一次求到一个时,按照下列的方式产生相应的新,即当被插入在任何两点间的最短路径时,被记录在中,依次求时求得,可由来查找任何两个点之间的最短路径。(2)FLOYD算法查找最短路径的方法:如果,那么点是点到点的最短路的中点。用同样的方法再查找,如果:(1)向点查找得:,,...,。(2)向点查找得:,,...,。那么从点到的最短路径为:,,...,,,,,...,,3.23FLOYD算法的算法步骤Floud算法算法目的:求任意两个顶点间的最短路径。:表示到之间的距离。:表示到之间的插入点。起始:选定带权值的邻接矩阵(1)赋值:对所有的,,,,1。(2)更新,对所有的,,如果,那么,。(3)如果=,那么算法终止;否则,再次回到(2),以此类推。3.24FLOYD建模应用举例某个城市要建立一个消防站,为该城市所属的七个区服务,如图所示。问应该把这个消防站设置在哪个区,才能使该消防站到最远的区的路径最短。用Floyd算法求出各点之间的距离,得到表格:0351075.57302742.54520524.5610750378.57423045.55.52.54.57401.57468.55.51.50从上表可以得出距离矩阵计算在各点设立服务设施的最大服务距离,。,,,,,,由于=那么应该将消防站设置在处。上述Floyd算法的MATLAB算法代码为:clear:w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,1.5,0];[d,r]=floyd(w)S=max(d’)%求矩阵各列的最大值s=min(S)3.
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2030年中国空气干燥净化机行业营销动态与需求前景预测报告
- 2024-2030年中国稻米油市场供给趋势及未来销售渠道研究研究报告
- 2024-2030年中国移动医疗行业市场发展分析及前景趋势与投资研究报告
- 2024-2030年中国科技地产市场运营格局与前景战略建议研究研究报告
- 2024-2030年中国离子色谱仪发展现状及趋势前景预判研究报告
- 2024-2030年中国磁选机行业发展前景预测和投融资分析研究报告
- 2024-2030年中国碳膜瓷棒行业市场运营模式及未来发展动向预测研究报告
- 2024-2030年中国硬泡聚醚行业专项调研与投资策略深度调查研究报告
- 2024-2030年中国硫酸行业需求潜力与发展方向预测报告
- 2024-2030年中国硫吸附剂行业现状调查及发展趋势研究研究报告
- 5吨龙门吊安装与拆除专项施工方案
- 一年级下册音乐教案-1(音乐游戏)小鹿小鹿-湘教版
- 快递业务员基础知识部课件
- 机械基础 第2版全书电子教案
- 齿轮轴工艺过程卡片
- 《少儿美术绘画课件》7岁 彩墨线描 《水母》
- 下肢动脉硬化性闭塞症课件
- 中医辨证治感冒课件
- 26个英文字母书写笔顺动态教学课件-26
- 摄影全套教程课件
- 小学数学北师大二年级上册七分一分与除法《分物游戏》李静
评论
0/150
提交评论