图论在实际生活中的应用

摘要在这个快节奏的时代，找到通往你想去的地方的最短路径变得越来越重要。这对节约人们的时间和成本具有重要意义。目前，城市规模越来越大，交通状况越来越复杂。从一个地方到另一个地方可能有许多种路径。如何从众多路径中选择最短路径或在所需时间内选择最短路径成为人们关注的焦点。能够选择最合适的道路将给我们的日常生活带来极大的便利。本文以重庆邮电大学为例，介绍了经典的Floyd算法及其实现。关键词：最优路径，弗洛伊德算法，路径发现一、图论的基本知识图论起源于世界著名的柯尼斯堡七桥问题。在哥尼斯堡的普洛伊格河上，有七座桥将河中的岛屿和小岛与河岸连接起来。一个问题是从四个陆地中的任何一个开始，穿过每座桥，只经过一次，然后回到起点。然而，许多人在无数次尝试后都失败了。欧拉在1736年神奇地解决了这个问题。他用快照分析的方法把这个问题转化为第一个图论问题：用点来代替每一片土地，用一条连接相应两点的线来代替每一座桥，所以它相当于得到一个“图”(下图)。CABD(b)哥尼斯堡的七座桥欧拉证明了这个问题没有解，并对这个问题进行了扩展，给出了一个给定图可以以某种方式通过的判断规则。这项工作使欧拉成为图论(和拓扑学)的创始人。图论也是一种应用数学。它的概念和结果来自广泛的来源，既来自生产实践，也来自理论研究。它有以下特点：它包含丰富的思想，美丽的图形和巧妙的证明；所涉及的问题是多方面的。问题的出现很简单，但本质却非常复杂和深刻。这个问题的解决方案是不断变化的，非常灵活，通常一个问题有一个解决方案。图论研究的内容非常广泛，如图的连通性、遍历性、计数、着色、极值和平面性等。在历史上，许多有才华的数学家和业余爱好者都参与了图论的研究。那么什么是图论中的图呢？在日常生活、生产活动和科学研究中，人们经常用点来表示事物，点与点之间是否有联系来表示事物之间是否有一定的关系。这样形成的图是图论中的一个图。事实上，集合论中二元关系的关系图都是图论中的图。在这些图中，人们只关心点之间是否有联系，而不关心点的位置和联系的优点。这是图论中的图和几何中的图之间的本质区别。因此，在现实世界中，许多事物的状态可以用图形来描述，使它们简单直观，易于理解，有助于思考，易于记忆。同时，可以根据图形的特点，从不同的角度扩展讨论范围。1.1。图论概述图论是数学的一个分支，也是一门新学科。它发展迅速，应用广泛。它已广泛应用于几乎所有学科，如物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等。另一方面，随着这些学科的发展，特别是计算机科学的迅速发展，图论的发展得到了极大的推动。图论中的研究对象是由若干给定点和连接两点的直线组成的图。这个图形通常用来描述某些事物之间的特定关系，点代表事物，连接两点的线代表两个相应事物之间的关系。1.2图论中的最短路径问题路径的定义被设置为顶点和边的交替序列的无向校准图调用的路径，其中的端点分别称为起点和终点，中的边数称为其长度，如果有另一个，则称为循环。如果的所有边都不同，它们被称为简单路径。如果有另一个，它被称为简单循环。如果所有的顶点(可能与相同的除外)都不同，并且所有的边都不同，则称为主路径。如果有另一个，那就是主循环。奇数长度的循环称为奇数循环，偶数长度的循环称为偶数循环。我们要考虑的问题是找到任何给定加权图的最短路径和两个方向的顶点之和。容易看见。只要考虑简单连通图的情况。这里我们假设每一边的重量是一个大于0的实数。因为当一边的重量是0。我们可以合并成一个顶点。此外，我们已经同意，我们将只接受它一劳永逸。1.3弗洛伊德算法弗洛伊德算法的基本思想：这个问题可以分解为先找到最短距离，然后考虑如何找到相应的路线。如何找到最短路径仍然是基于动态规划的知识。对任何地方来说，我和J之间的最短距离只不过是通过我和J之间的K而不通过K的可能性。因此，有可能使k=1，2，3，n(n是位数)并检查d(ij)和d(ik) d(kj)的值。这里，d(ik)和d(kj)分别是迄今已知的最短距离I到k和k到j，因此d(ik) d(kj)是通过k的最短距离I到j。因此，如果存在d(ij)d(ik) d(kj)，则意味着从I到k到j的距离比从I到j的原始距离短。自然地，I到j的d(ij)被重写为d(ik) d(kj)。每次检查K时，d(ij)是从I到J的最短距离。重复此过程，最后当检查所有K时，I和J之间的最短距离存储在d(ij)中。弗洛伊德算法的基本步骤：定义方阵序列d-1，d0，dn-1 of nn，初始化：d-1=cD-1 I j=边长，表示从I到j的初始最短路径长度，即从I到j的最短路径，不经过其他中间点。迭代：假设已经找到Dk-1，如何得到Dk(0kn-1)代表最短路径.中间p:ij从I到j不大于k-1。考虑将顶点k添加到路径p，以获得顶点序列q: I.k.j，如果q不是一条路径，当前最短路径仍然是前一步的结果：dkIj=dk-1Ij；否则，如果q的长度小于p的长度，则使用q代替p作为从I到j的最短路径。因为两条子路径I.k和k.q的j都是中间点不大于k-1的最短路径，中间点不大于k的从I到j的最短路径长度为：DkIj=最小 Dk-1ij，Dk-1ik Dk-1kj 2.利用图论知识寻找指定两点最短路径2.1将实际问题转化为图论问题图1重庆邮电大学地图上图是邮电大学的地图。我们在地图上选择了cyit中的八个地方作为八个点(1、新世纪超市2、三栋教学楼3、数字图书馆4、两栋教学楼5、信息技术楼6、太极操场7、老图书馆8和31个宿舍)，并用线段将每个点与其相邻点连接起来，形成一张无向地图。根据实际情况：不同地点之间的距离；道路是否畅通对相应的边赋予权重，最终得到一个加权图，如图2所示：图2加权图2.2弗洛伊德算法在c语言中实现#包括#包括#包括使用命名空间标准；#定义最大值_值_数值10向量全路径；/矢量，用于存储从顶点A到顶点I的所有路径向量全部；/存储相应路径长度的向量结构图最大烦恼；最大凸数最大凸数；int vexnum，arcnum；图G；int Locatevex(图G，char v)/图的基本运算，求v的位置int I=0；而(Ig . VexNumG . arcnum；请输入顶点的名称(0-9)“一世”。对于(int q=0；qv1v2weight。int a=Locatevex(G，v1)；int b=Locatevex(G，v2)；=重量；ba=ab；该图的邻接矩阵表示为：