图论论文_Floyd算法的应用

题目Floyd算法在旅游线路制定问题中的应用学院姓名学号2010年11月摘要随着日益增长的精神文化需求，旅游已经逐渐成为人们假期生活中不可缺少的一部分。但是旅游的高费用和经济条件还有时间的限制也制约着人们的旅行计划。尤其是对于我们这种初到某城市的学生游客，旅行路线的制定就成为了一个重要的问题。如何在有限时间内经济实惠地制定自己的旅行计划需要我们用有效的数学手段来解决。通过对《图论》这门课程的学习，发现各种最短路径的算法都能够很好的解决实际生活中的问题，例如Dijkstra算法、Floyd算法、Bellman-Ford算法等等。本文主要介绍了Floyd算法的原理，以重庆市周边旅游景点为背景，选取了几个计划之内的旅游景点为假设模型，希望通过Floyd算法获得任意两景点之间的最短路径来制定旅游路线，中间路过的景点也是我们计划之内的。关键词：Floyd算法最短路径假设模型距离估算最小权重绪论在18世纪30年代。一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题要求遍历普鲁士的哥尼斯堡七桥中的每一座桥恰好一次后回到出发点。欧拉证明了这是不可能完成的。此后，欧拉发表了著名的论文《依据几何位置的解题方法》，这是图论领域的第一篇论文，标志着图论的诞生。图论的真正发展始于20世纪五六十年代之间。是一门既古老又年轻的学科，图论极有趣味性，严格来讲它是组合数学的一个重要分支。虽然图论只是研究点和线的学问。但其应用领域十分广阔。不仅局限于数学和计算机学科，还涵盖了社会学、交通管理，电信领域等等。总的来说，图论这门学科具有以下特点：图论蕴含了丰富的思想，漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化，非常灵活，常常是一种问题一种解法。由以上三个特点可以看出。图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的理论体系和解决问题的系统方法。而且图论所研究的内容非常广泛，例如图的连通性、遍历性。图的计数。图的着色、图的极值问题。图的可平面性等等。最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用等问题，都可以通过建立最短路问题模型来求解。最短路问题一般是在加权图中讨论，最短路径不仅仅是指一般意义上的距离最短，诸如时间、费用都可以被引申为最短路径，相应的最短路径问题就成了最快路径问题、最低费用问题等。1背景介绍重庆是中华人民共和国四个直辖市之一，地处中国西南。是中国重要的中心城市之一，历史悠久，国务院公布的第二批国家历史文化名城之一。因为重庆的地理环境，重庆多山多雾，故又有雾都、山城的别名。重庆也是旅游胜地，周边大大小小的旅游景点数不胜数。例如大足石刻、钓鱼城、丰都、小田溪巴王墓群、金佛山、歌乐山等等。对于我们这些初到重庆的学生游客来说，由于对当地理环境并不熟悉，而且时间有限。我们希望在有限的十一或是五一假期内，找到最短的最经济的旅游线路，进行一次重庆周边旅行。所以，如何制定旅游线路就是一个很重要的问题。通过对《图论》这门课程的学习，我们知道最短路径也是图论中的一个重要的应用问题。其中涉及到的各种算法在日常生活中得到了广泛的应用。Floyd算法就是任意两点间最短路径的经典算法。2Floyd算法描述2.1最短路径问题在图G中的每一条边，可赋以一个实数()we，称为e的权，G连同它边上的权称为赋权图，赋权图经常出现在图论的应用中。例如在友谊图中，权可以表示友谊深度；在通信图中，权可以表示各种通讯线路的建造或维修费用。若H是赋权图的一个子图，则H的权()wH是指它的各边的权和。许多最优化问题相当于要在一个赋权图中找出某类具有最小（或最大）权的子图，其中之一就是最短路问题：就是要在一个赋权图的两个指定顶点ou和ov之间找出一条具有最小权的路。最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用。顶点对之间的最短路径是指：对于给定的有向网(,)GVE，要对G中任意一对顶点有序对,()VWVW，找出V到W的最短距离和W到V的最短距离。目前，关于最短路问题的研究已有较多结果，传统的最短路算法主要有Floyd算法和Dijkstra算法等。其中，Dijkstra算法求解任意顶点对之间最短距离的方法是：轮流以每一个顶点为源点，重复执行算法n次，即可求得每一对顶点之间的最短路径，总的时间复杂度为3()on，Floyd提出了另外一个求图中任意两顶点之间最短路径的算法，虽然其时间复杂度也是3()on，但其算法的形式更简单，易于理解和编程。2.2Floyd算法描述对于图G，如果(,)wij表示i和j之间的可实现的距离，那么(,)wij表示端i和j之间的最短距离当且仅当对于任意的i,j,k，有(,)(,)(,)wijwikwkj。该算法用矩阵形式来表示，并进行系统化的计算，通过迭代来消除不满足上述定理的情况，对于n个端，一给定边长ijd的图，顺序计算各个nn的W阵和R阵，前者代表径长，后者代表转接路由。其步骤如下：0F：置(0)(0)[]ijijWw其中和0(0)[]ijRr其中1F：已得(1)kW和(1)kR阵，求()kW和()kR阵中的元素如下2F：kn，重复1F；k=n，终止。由上述步骤可见，(1)()kkWW是计算经kv转接时是否能缩短经常，如有缩短，更改ijw并在R阵中记下转接的端。最后算得()nW和()nR，就得到了最短径长和转接路由。0,,0ijijijijdvvwvvij有边无边(0)(0)(0)0ijijijwjrwij或()(1)(1)(1)min[,]kkkkijijikkj(1)()(1)(1)(1),,kkkijijijkijkkkikijijrwwrrww若若3Floyd算法用于解决旅行线路问题3.1旅行线路模型假设初到重庆邮电大学，同学们对重庆这个历史悠久且极具特色的中国中心城市充满了好奇，在节假日的时候都计划着去重庆市周边的旅游景点进行短期旅行。由于我们对重庆市的地理环境消费水平等并不是特别了解，制定旅行线路就成为了一个很重要的问题，由于假期时间有限，我们希望能够在备选目的地景点中，能够找到任何两个景点之间的最短路，且中途经过的节点也是备选景点中的景点。于是选择重庆周边的各个景点为对象如图3-1所示，我们可以选择图示的任何几个景点来生成一个考察对象图，图中粗线条所连接生成的图为文章中考察的图，命名为G。图3-1重庆市周边旅游景点图图中选择的备选景点分别为：大足石刻、钓鱼城、丰都、小田溪巴王墓群、金佛山、歌乐山、重庆市中心。这七个景点依次编号为1-7，且如图所示粗线表示连接端点的边分别命名为1v-7v。于是我们生成了考察对象图G，如图3-2所示。通过考察各个景点之间的实际距离（公里数），1e-10e的公里数分别为：78.6km，293.2km，175.6km，176.1km，129.2km，17.9km，79.8km，236.9km，124.7km，20.2km。我们以最短距离20.2为基准作归一化处理得到近似1e-10e的值分别为：4，14，9，9，6，1，4，12，6，1。假设模型中，用这些归一化的值分别代表各个边的权值，构成加权图G如图3-2所示。图3-2由七个景点生成的图G3.2用Floyd算法计算任意两景点之间的最短路径现在我们以上述生成的图G为考察对象，根据算法流程，设W阵和R阵分别代表径长和转接路由。那么计算结果如下：1v2v3v4v5v6v7v1e2e3e4e5e6e7e8e9e10e(0)0414014414099091290661601412610W(0)0200060103000702040000030507000406710005070204560R(1)0414014(5)414099091290661(5)601412610W(1)020006010300(1)70204000003050700040671(1)005070204560R(2)04(18)1(8)401454(18)1409(19)(18)90912906615(19)601(8)4(18)12610W(2)02(2)006(2)1030017(2)2040(2)(2)0030507000406711(2)0507(2)2(2)4560R(3)0418(27)184014(23)541814091918(27)(23)909(28)1290661519(28)601841812610W(3)022(3)062103(3)0172204022(3)(3)305(3)70004067112(3)5072224560R(4)041827(36)18401423(32)54181409(18)191827239092812(36)(32)(18)9066151928601841812610W(4)0223(4)621033(4)172204(4)223330537(4)(4)(4)406711235072224560R(5)041827361840142332541814091819182723909(15)1236321890661519(15)601841812610W(5)02234621033417220442233305(5)74444067112(5)5072224560R(6)0418(16)(7)1(2)4014(20)(11)54181409181918(16)(20)9091512(7)(11)189066151915601(2)41812610W(6)022(6)(6)6(6)103(6)(6)172204422(6)(6)30557(6)(6)440671125507(6)224560R(7)0418(14)7124014(16)(10)54181409181918(14)(16)909(13)127(10)1890661519(13)601241812610W(7)022(7)666103(7)(7)172204422(7)(7)305(7)76(7)44067112(7)5076224560R经过7轮迭代，我们得到了最终的W和R阵，分别包含了径长信息和路由信息。我们可以从(7)M和(7)R中找到任何两个端点间的最短径长和最短路由，对应着我们所建立的旅行线路模型中的任何两景点间的最短路径长度和路线。例如我们要找从丰都到大足石刻的最短路径以及路线长度，也就对应着节点3v到1v的最短路径和径长，可以从(7)M中找到对应的最小值为18，从(7)R中找到312r，就是要经2v转接；再看211r，此时已经到达目的节点，所以路由是321vvv，对应模型中的景点为丰都经钓鱼城到大足石刻，总公里数为1820.2363.6km。综上所述，我们可以任选几个备选景点，然