图论在实际生活中的应用

1、寻找最短的路径到达想要去的地方在这个快节奏的时代己经变得越來越重要，它对于节约人们的时间成本具有重要意义。当前城市的规模越來越大，交通道路状况也越來越复杂，从一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的日常生活带來极大地方便。本文就通过找重庆邮电大学儿个代表性地点之间寻找最短距离路径为例，介绍经典的最短路径算法Floyd算法及其算法的实现。关键字：最优路径，Floyd算法，寻路论的基本知识图论起源于举世闻名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上面有七座桥将河中的岛及岛与河岸是连接起

2、來的,有一个问题是要从这四块陆地中任何一块开始，通过每一座桥而且正好只能一次，再回到起点。然而许多人经过无数次的尝试都没有成功。在1736年欧拉神奇般的解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即用点來代替每一块陆地，将每一座桥用联接相应的两个点的一条线來代替，所以相当于得到一个“图”（如下图）。柯尼斯堡七桥图桥转换成图欧拉证明了这个问题是没有解的，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使得欧拉成为图论（及拓扑学的创始人。图论其实也是一门应用数学，它的概念和结果來源非常广泛，既有來自生产实践的问题，也有來自理论研究的问题。它具有以下特点

3、：蕴含了丰富的思想、漂亮的图形以及巧妙的证明；涉及的问题很多而且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法是千变万化，非常灵活，常常是一种问题就有一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。历史上参与研究图论问题的人既有许多天才的数学家，也有不少的业余爱好者。那么什么是图论中的图呢？在日常生活、生产活动以及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否是有某种关系，这样构成的图形就是图论中的图。其实，集合论中的二元关系的关系图都是图论中的图，在这些图中，人们只关心点与点之间是否有连线，而不关

4、心点的位置，以及连线的曲直。这就是图论中的图与几何中的图形的本质区别。因此在现实世界中，事物的许多状态可以由图形来描述，使其简单直观，便于理解，帮助思维，易于记忆，同时还可以根据图的特点，从不同角度來扩展讨论范围。1.K图论概述图论(GraphTheory)是数学的一个分支，也是一门新兴学科，发展迅速而又应用广泛。它己广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等儿乎所有的学科领域。另一方面，随着这些学科的发展，特别是计算机科学的快速发展，乂大大的促进了图论的发展。图论中的研究对象是由若干给定的点及连接两点的线所构成的图形，这种图形通常用來描述某些事物

5、之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。1.2图论中的最短路问题路的定义设&为无向标定图，G中顶点与边的交替序列了=%勺必2勺称为到的通路,其中v也，为勺的端点，心12,/,气,分别称为T始点、与终点、,丁中的边的条数称为它的长度，若乂有%,则称厂为回路。若丁的所有边各异，则称了为简单通路。若又有v宀，则称厂为简单回路，若所有的顶点(除与可能相同外)各异，所有的边也各异，则称厂为初级通路或路径，若乂有=人，则厂为初级回路或圈，将长度为奇数的圈成为奇圈，长度为偶数的圈为偶圈。我们要考虑的问题是对任意给定的一个赋权图G,及G中两个指点的顶点。与求出其最短路径

6、。易见。只要考虑简单连通图的情形就够了。这里我们假设每边的权都是大于0的实数。因为当一条边的权为o时。我们可以把和v合并成一个顶点。又，我们约定边兀E(G)当且仅当(e)=coo1.3Floyd算法Floyd算法的基本思想：可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个地点而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=l,2,3,n(n是地点的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离,因此d

7、(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-1,DO,Dnl,初始化：D-1=CD-lij=边0上的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。迭代：设Dk-1己求出，如何得到Dk(OWkWn-l)Dk-1i

8、j表示从i到j的中间点不大于k-1的最短路径p：j,考虑将顶点k加入路径p得到顶点序列q：ikj,若q不是路径，则当前的最短路径仍是上一步结果：Dkijl=Dk-否则若Q的长度小于P的长度，则用q取代P作为从i到j的最短路径。因为q的两条子路径ik和k-j皆是中间点不大于k-1的最短路径,所以从i到j中间点不大于k的最短路径长度为：Dkij=minDk-lijl,Dk-lik+Dk-lkj二、利用图论知识寻找指定两点最短路径2.1把实际问题转化成图论问题图1重庆邮电人学地图上图为邮电大学的地图，我们在地图中选取重邮的八个地方看成是八个点(1、新世纪超市2、三教学楼3、数字图书馆4、二教学楼5、

9、信科大楼6、太极操场7、老图书馆8、31栋宿舍），用线段把每一个点与其相邻的点连接起來，从而形成一个无向图。再根据实际情况：不同地点的距离问题；路的畅通与否等给相应的边赋上权值，最后得出一个赋权图，如图2：图2赋权图2.2Floyd算法用C+实现iiicludeiiicludemcludeusingnamespacestd;#defineMAX_VEX_NUM10vectorallPath;向量:，用来存放所有的顶点a到顶点i的路径vectorall;/向量，用来存放对应路径的长度stmctMGraphchai-vexsMAX_VEX_NUM;mt如csMAX_VEX_NUMMAX_VEX_N

10、UM;intvexiiuni.aicnum;MGraphG;mtLocatevex(MGiaphGcharv)/图的基本操作，寻找V的位置mt1=0;while(iG.vexiium&v!=G.vexsi)if(iG.vexnum)returni;elsereturn-1;mtCreateUDG(MGiaph&G)/数组邻接矩阵表示法构造无向图clwvl,v2;intweight;cout请输入图的顶点数和边的条Sendl;ciiiG.vexiiumG.arcnum;cout请输入顶点的名称(0-9)”endl;fbr(inti=0;iGvexnum;i+)cinG.vexsi;fbi(iii

11、tq=0:qG.vexiiuni;q+)for(mtp=0;pG.vexnum:p+)G.aicsqp=0;for(iiitk=0;kG.aicnum;k+)/构造邻接矩阵coutvv，输入边的顶点和权值：(格式为：起点终点权值)irendl;ciiivlv2weight;inta=Locatevex(G；v1);intb=Locatevex(G；v2);G.aicsab=weight;Garcsba=Garcsab;cout该图的邻接矩阵表示为：n“；fbr(mtn=0;nGvexnum;n+)/输出顶点coutGvexsnHH;coutM(矩阵顶点名称)”；coutendl;coutend

12、l;for(intx=0;xGvexnum;x+)输出邻接矩阵foi(mty=O;y”+v亡xs;allPath.push_back(path);all.push_back(Long);coutM路径:Hpathn长度:HLongendl;elsepath=path+”一”+v亡xs;mti=Locatevex(G；vexs);visitedi=tme;for(intj=0JGvexiium;j+)if(!visitedj)&(Garcsij!=0)Miiiway(G；visited,G.vexsjXong-TiarcsijArb.path);visitedi=false;voidCountM

13、inwav(MGiaphG)该函数调用递归部分实现递归charva,vb;strmgpath:cout请输入您所处的位置:”；ciiiva;cout请输入您想到达的位置:”；ciiivb;coutendl;iiiti=Locatevex(G；va);boolvisited100;fbr(intj=0JGvexnumJ+)visitedj=false;visitedi=tme;intLong=0;path+=vra;fbr(j=0JG.vexiiumJ+)if(GarcsiIj!=0)Long=GarcsiIj;Mmvay(G.visited,G.vexsj,Long.vb.path);cout

14、endl;voidMinwayQ/输出报短路径intmm=10000;fbr(inti=O;iallPath.sizeQ;i+)niiii=alli;fbr(intj=OjallPath.size0J+)coutn最短路径:liallPatlijli长度:Halljendl;coutendl;voidmain()CieateUDG(G);建图CountMiiiway(G);找出所有路径MinwayO;输出最短路径程序描述：通过输入顶点的个数、边的条数和名称以及两点之间的权值得到一个带权值的矩阵。再输入你所处的位置和你要到的位置，程序将通过Floyd算法给出可以到达的路径，并给出最优的路径(即权

15、值最小的路径)。输入图的顶点个数和边的条数，并输入顶点的名称如图3所示。813h青输入顶点的名称5Q12356?8图3数据输入图输入边的权值，输入格式为边的起点名称终点名称和权值，如图4所示。输入边的顶点和权值，啼式为，起点终点权值L58输入边的顶点和权值格式为起点终点权值33输入边的顶点和权值，啪式为，起点终点权值L25输入边的顶点和帝试为三起点终点衩值356输入边的顶点和权值：格式为：起点终点权值343输入边的顶点和权值，啼式为，起点终点权值365输入边的顶点和权值格式为起点终点权值263输入边的顶点和权值，啪式为，起点终点权值453输入边的顶点和帝试为三起点终点衩值471输入边的顶点和权

16、值：格式为：起点终点权值573输入边的顶点和权值，啼式为，起点终点权值&?4输入边的顶点和权值格式为起点终点权值683输入边的顶点和权值，啪式为，起点终点权值?83图4权值的输入程序自动生成并输出图的邻接矩阵如图5所示。该图的邻按矩阵表示为：123456781度2度度8度0度5度一长1:2长1长1:1长1:1长1:1长225204霁曉20丄虞625度长:15度.:11长2:1:11长26雲长:255虞:15度山度皿1?13355_-3_-4_一5_-6_33长164度31145i度45444455533:8置位的啲歴处到您您IJA1A677專llmlltstiIgllAl-IImlmllt鑽!?最短路径:图6输出结果总结图论其实是一门应用数学，它的概念和结果來源非常广泛，既有來自生产实践的问题，也有來自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化。非常灵活，常常是一种问题一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性