图论最短路径分析及应用

最短路径问题的分析与应用专家：信息和计算科学类别：组成员：2012年06月23日，北京摘要：介绍了最短路的两种算法： Dijkstra和Floyd。 这两种算法在实际问题中的应用和比较。关键词：图论、最短路径、戴克斯特(戴克斯特)、弗洛伊德(弗洛伊德)最短路问题及其应用1引言图论是应用数学的分支，其概念和结果来源非常广泛，最早是数学游戏的难题研究，如欧拉解决的哥白尼七桥问题、民间广泛传播的游戏难题，如迷宫问题、游戏问题、盘上马步行道问题等。 这些老难题当时引起了许多学者的关注。 在这些问题研究的基础上，继续提出着名的四色猜想和汉密尔顿(世界一周)数学难题。1847年，图论应用于电路网络的分析。 它最初应用于工程科学，随着科学的发展，图论在解决运营规划学、网络理论、信息论、控制理论、博弈论、计算机科学等各个领域的问题中发挥了越来越大的作用。 在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等诸多领域问题的有力工具之一。最短路的问题是图论理论的典型问题。 搜索最短路径是在指定的网络中找到两个节点之间距离最小的路径。 最短的不仅仅是一般的地理距离最短，还能谈到时间、费用、线路容量等其他测量标准。选择和实现最短路径算法是路径设计的基础，最短路径算法是计算机科学和地理信息科学等领域的研究热点，许多网络相关问题可以归入最短路径问题的范畴。 经典图论与不断发展的完善计算机数据结构和算法的有效结合不断出现新的最短路径算法。2最短短路2.1最短路径的定义对最短路问题的研究早在1960年代以前就有效，其中对权利图有效的算法是荷兰着名计算机专家e.w.dickstra于1959年首次提出的，该算法能够解决两个指定点之间的最短路，从图g中的某个特定点到其他各顶点随后赫斯渥基于Dijkstra算法提出了赫斯渥算法。 然而，两种算法都不能解决包含负权重的图的最短路问题。 因此，Ford提出了Ford算法，能够有效地解决包括负权利在内的最短路问题。 但是在现实生活中，我们面临的问题大多不包括负面的权利，所以我们有时会选择Dijkstra算法。定义1对图G=G(V，e )的各边e赋予实数W(e )，称为边e的权重，此图称为加权图，标记为G=G(V，e，w )。定义2图G=G(V，e )为加权图，如果是u到达的道路的权重，则将的长度、长度最小的道路称为最短路。要找到来自的通道，请使全长最短，也就是说。2.2最短问题算法的基本思想和基本步骤用于确定网络上的节点之间的最短路径的方法中，当前国内外公认的一种良好算法是Dijkstra和Floyd算法。 在这两种算法中，网络被抽象化为由一个曲线图逻辑所定义的有向曲线图或者无向曲线图，利用曲线图的节点相邻矩阵来记录点间的相关信息。 如果针对最短路径执行图形扫描以找到它，则继续确定目标值的最小性能，直到获得最后的最优路径为止，基于此矩阵。Dijkstra算法是图论中确定最短路的基本方法，也是其他算法的基础。 为了确定赋权图中任意两个节点之间的最短路径，通常采用两种方法。 一种方法是将一个节点作为起点重复执行Dijkstra算法n次。 另一种方法是Floyd在1962年提出的Floyd算法，其时间复杂度与Dijkstra算法重复执行n次的时间复杂度相同，但其形式简单，实际运算效果优于前者。Dijkstra算法的基本步骤：令：并令： 1对了，拜托了求求你令如果找到的最短距离不是，则从中删除旋转1经过有限次迭代确定的最短路径可以用如下流程图表示第一步，首先意味着的距离为0，是给定的初始值。在步骤2中，利用已知数据对进行修改。在步骤3中，求出全部修正后的最小值。 其对应点是可以一步一步到达的店中最近的，因为一切。 因此，由于从其他点开始中继到达的路径上的距离大于直接到达的距离，因而根据算法从s中进行删除，若k=n则设为最短路径，计算结束。 否则返回第二部分，计算运算直到k=n。这样每次反复得到到一点的最短距离，重复上述过程。Floyd算法的基本原理和实现方法，若表示矩阵中I和j的距离，则在I和j之间陷入无穷大。 I与j之间的最短距离可以是n，其中n是节点的数目，因为I与j之间的最短距离可以穿过或不穿过I与j之间的k。 和的值，其中分别是从I到j的最短距离，因为I到k和j的当前已知的最短距离是k。 因此，如果显示从I经过k到j的距离比从原来的I到j的距离短的话，自然会写出从I到j。 每次搜索k时，都是当前I到j的最短距离。 重复此过程，最后检查所有k，得到从I到j的最短距离。3最短路的应用程序例2从北京(Pe )乘飞机到东京(t )、纽约(n )、墨西哥城(m )、伦敦(l )、巴黎(pa ) 5个城市旅行，每个城市刚好回到北京，如何安排旅行线路使旅行最短，各城市间的航线距离如下表所示lmn公共汽车Pet.tl5635215160m5621577870n3521366868公共汽车2157365161Pe5178685113t.t6070686113解：程序如下：clc，cleara (1，2 )=56； a (1，3 )=35； a (1，4 )=21； a (1，5 )=51； a (1，6 )=60；a (2，3 )=21； a (2，4 )=57； a (2，5 )=78； a (2，6 )=70；a (3，4 )=36； a (3，5 )=68； a (3，6 )=68；a (4，5 )=51； a (4，6 )=61；a (5，6 )=13；a (6， )=0；a=a；c1=5 1:4 6；L=length(c1)flag=1；while flag0flag=0；for m=1:L-3for n=m 2:L-1if a(c1(m )，c1(n) a(c1(m 1)，c1(n 1)0flag=0；for m=1:L-3for n=m 2:L-1if a(c1(m )，c1(n) a(c1(m 1)，C1 (n1) )是.a(