《图论在实际生活中的应用》由会员分享，可在线阅读，更多相关《图论在实际生活中的应用（10页珍藏版）》请在金锄头文库上搜索。
1、寻找最短的路径到达想要去的地方在这个快节奏的时代已经变得越来越重要，它对于节约人们的时间成本具有重要意义。当前城市的规模越来越大，交通道路状况也越来越复杂，从一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的日常生活带来极大地方便。本文就通过找重庆邮电大学几个代表性地点之间寻找最短距离路径为例，介绍经典的最短路径算法Floyd算法及其算法的实现。关键字：最优路径，Floyd算法，寻路一、图论的基本知识图论起源于举世闻名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上面有七座桥将河中的岛及岛与河岸是
2、连接起来的,有一个问题是要从这四块陆地中任何一块开始，通过每一座桥而且正好只能一次，再回到起点。然而许多人经过无数次的尝试都没有成功。在1736年欧拉神奇般的解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即用点来代替每一块陆地，将每一座桥用联接相应的两个点的一条线来代替，所以相当于得到一个“图”（如下图）。柯尼斯堡七桥图桥转换成图C欧拉证明了这个问题是没有解的，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使得欧拉成为图论及拓扑学的创始人。图论其实也是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以
3、下特点：蕴含了丰富的思想、漂亮的图形以及巧妙的证明；涉及的问题很多而且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法是千变万化，非常灵活，常常是一种问题就有一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。历史上参与研究图论问题的人既有许多天才的数学家，也有不少的业余爱好者。那么什么是图论中的图呢？在日常生活、生产活动以及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否是有某种关系，这样构成的图形就是图论中的图。其实，集合论中的二元关系的关系图都是图论中的图，在这些图中，人们只关心点与点之间是否有连线，
4、而不关心点的位置，以及连线的曲直。这就是图论中的图与几何中的图形的本质区别。因此在现实世界中，事物的许多状态可以由图形来描述，使其简单直观，便于理解，帮助思维，易于记忆，同时还可以根据图的特点，从不同角度来扩展讨论范围。1.1、图论概述图论GraphTheory是数学的一个分支，也是一门新兴学科，发展迅速而又应用广泛。它已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等几乎所有的学科领域。另一方面，随着这些学科的发展，特别是计算机科学的快速发展，又大大的促进了图论的发展。图论中的研究对象是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些
5、事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。1.2图论中的最短路问题路的定义设G为无向标定图，G中顶点与边的交替序列Tveveevi0j1i1j2jlil称为vi0到爲的通路，其中,，vi为ej的端点，丫I2vi0V分别称为T始点与终点，T中的边的条数称为它的长度，若又有vo=，贝V称T为回路。若T的所有边各异，贝V称T为简单通路。若又有vo=，贝V称T为简单回路，若所有的顶点(除0与可能相同外)各异，所有的边也各异，则称T为初级通路或路径，若又有0=，则T为初级回路或圈，将长度为奇数的圈成为奇圈,长度为偶数的圈为偶圈。我们要考虑的问题是对任意给定的一个
6、赋权图G，及G中两个指点的顶点Uo与Vo，求出其最短路径。易见。只要考虑简单连通图的情形就够了。这里我们假设每边e的权w(e)都是大于0的实数。因为当一条边euv的权为0时。我们可以把u和v合并成一个顶点。又,我们约定边e,E(G)当且仅当w(e)=g。1.3Floyd算法Floyd算法的基本思想：可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个地点而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是地点的数目)，在检查d(ij)与d(ik)+d(kj)的值；
7、在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有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时，d(ij)里面存放的就是i到j之间的最短距离了。Floyd算法的基本步骤：定义nXn的方阵序列D-l,DO，Dn1,初始化：D-1=CD-1ij=边i,j的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他
8、中间点的最短路径。迭代：设Dk-1已求出，如何得到Dk(OWkWn-1)Dk-1ij表示从i到j的中间点不大于k-1的最短路径p：ij,考虑将顶点k加入路径p得到顶点序列q：i-k-j，若q不是路径，则当前的最短路径仍是上一步结果：Dkij=Dk1ij;否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。因为q的两条子路径i-k和k-j皆是中间点不大于k1的最短路径,所以从i到j中间点不大于k的最短路径长度为：Dkij=minDk-1ij,Dk-1ik+Dk-1kj二、利用图论知识寻找指定两点最短路径2.1把实际问题转化成图论问题图1重庆邮电大学地图上图为邮电大学的地图，我们在地图
9、中选取重邮的八个地方看成是八个点(1、新世纪超市2、三教学楼3、数字图书馆4、二教学楼5、信科大楼6、太极操场7、老图书馆8、31栋宿舍），用线段把每一个点与其相邻的点连接起来，从而形成一个无向图。再根据实际情况：不同地点的距离问题；路的畅通与否等给相应的边赋上权值，最后得出一个赋权图，如图2：图2赋权图2.2Floyd算法用C+实现#includeviostream#includevvector#includeusingnamespacestd;#defineMAX_VEX_NUM10vectorallPath;向量，用来存放所有的顶点a到顶点i的路径vectorall;向量，用来存放对应路
10、径的长度structMGraphcharvexsMAX_VEX_NUM;intarcsMAX_VEX_NUMMAX_VEX_NUM;intvexnum,arcnum;MGraphG;intLocatevex(MGraphG,charv)图的基本操作，寻找V的位置inti=0;while(iG.vexnum&v!=G.vexsi)i+;if(iG.vexnumG.arcnum;coutvv请输入顶点的名称(0-9)vvendl;for(inti=0;ivG.vexnum;i+)cinG.vexsi;for(intq=0;qvG.vexnum;q+)for(intp=0;pvG.vexnum;p+
11、)G.arcsqp=0;for(intk=O;kv1v2weight;inta=Locatevex(G,v1);intb=Locatevex(G,v2);G.arcsab=weight;G.arcsba=G.arcsab;coutvv该图的邻接矩阵表示为：n;for(intn=O;nvG.vexnum;n+)输出顶点coutvvG.vexsnvv;coutvv(矩阵顶点名称)”；coutvvendl;coutvvendl;for(intx=O;xvG.vexnum;x+)输出邻接矩阵for(inty=0;yG.vexnum;y+)coutG.arcsxy;coutendl;coutendl;c
12、out+vexs;allPath.push_back(path);all.push_back(Long);coutvv路径:vvpathvv长度:vvLongvvendl;elsepath=path+-+vexs;inti=Locatevex(G,vexs);visitedi=true;for(intj=0;jva;coutvv请输入您想到达的位置:；cinvb;coutvvendl;inti=Locatevex(G,va);boolvisited100;for(intj=0;jvG.vexnum;j+)visitedj=false;visitedi=true;intLong=0;path+=
13、va;for(j=0;jG.vexnum;j+)if(G.arcsij!=0)Long=G.arcsij;Minway(G,visited,G.vexsj,Long,vb,path);coutendl;voidMinway()输出最短路径intmin=10000;for(inti=0;iallPath.size();i+)if(allimin)min=alli;for(intj=0;jallPath.size();j+)if(allj=min)coutvv最短路径：vvallPathjvv长度:vvalljvvendl;coutendl;voidmain()CreateUDG(G);/建图CountMinway(G);/找出
