图论在实际生活中的应用
摘 要
寻找最短的路径到达想要去的地方在这个快节奏的时代已经变得越来越重要，它对于节约人们的时间成本具有重要意义。当前城市的规模越来越大，交通道路状况也越来越复杂，从一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的日常生活带来极大地方便。本文就通过找重庆邮电大学几个代表性地点之间寻找最短距离路径为例，介绍经典的最短路径算法Floyd算法及其算法的实现。
关键字: 最优路径，Floyd算法，寻路
一、图论的基本知识
图论起源于举世闻名的柯尼斯堡七桥问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
。在柯尼斯堡的普莱格尔河上面有七座桥将河中的岛及岛与河岸是连接起来的,有一个问题是要从这四块陆地中任何一块开始，通过每一座桥而且正好只能一次，再回到起点。然而许多人经过无数次的尝试都没有成功。在1736年欧拉神奇般的解决了这个问题，他用抽像
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
法将这个问题化为第一个图论问题:即用点来代替每一块陆地，将每一座桥用联接相应的两个点的一条线来代替，所以相当于得到一个“图”(如下图)。
柯尼斯堡七桥图 桥转换成图
C
A D
B
(b)
欧拉证明了这个问题是没有解的，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使得欧拉成为图论〔及拓扑学〕的创始人。
图论其实也是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点:蕴含了丰富的思想、漂亮的图形以及巧妙的证明;涉及的问题很多而且广泛，问题外表简单朴素，本质上却十分复杂深刻;解决问题的方法是千变万化，非常灵活，常常是一种问题就有一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。历史上参与研究图论问题的人既有许多天才的数学家，也有不少的业余爱好者。
那么什么是图论中的图呢,在日常生活、生产活动以及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否是有某种关系，这样构成的图形就是图论中的图。其实，集合论中的二元关系的关系图都是图论中的图，在这些图中，人们只关心点与点之间是否有连线，而不关心点的位置，以及连线的曲直。这就是图论中的图与几何中的图形的本质区别。
因此在现实世界中，事物的许多状态可以由图形来描述，使其简单直观，便于理解，帮助思维，易于记忆，同时还可以根据图的特点，从不同角度来扩展讨论范围。
1.1、图论概述
图论〔Graph Theory〕是数学的一个分支，也是一门新兴学科，发展迅速而又应用广泛。它已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等几乎所有的学科领域。另一方面，随着这些学科的发展，特别是计算机科学的快速发展，又大大的促进了图论的发展。
图论中的研究对象是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
1.2 图论中的最短路问题
GG路的定义 设为无向标定图，中顶点与边的交替序列
T,veve？evi0j1i1j2jlil
vver,1,2,？,l,v,vvviijiii0ilr,1rr0l称为到的通路，其中，为的端点，分别称为
v,vii0lTTT始点与终点，中的边的条数称为它的长度，若又有，则称为回路。
v,vii0lTTT若的所有边各异，则称为简单通路。若又有，则称为简单回路，若
vvii0lT所有的顶点(除与可能相同外)各异，所有的边也各异，则称为初级通
v,vii0lT路或路径，若又有，则为初级回路或圈，将长度为奇数的圈成为奇圈，长度为偶数的圈为偶圈。
GG我们要考虑的问题是对任意给定的一个赋权图,及中两个指点的顶点uv00与，求出其最短路径。易见。只要考虑简单连通图的情形就够了。这里我
w(e)ee,uv们假设每边的权都是大于0的实数。因为当一条边的权为0时。我
e,E(G)w(e),,uv们可以把和合并成一个顶点。又，我们约定边当且仅当。
1.3 Floyd算法
Floyd算法的基本思想:
可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个地点而言，i到j的最短距离不外乎存在经过i与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)就是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算法的基本步骤:
定义n×n的方阵序列D-1, D0 , „ Dn,1,
初始化: D-1,C
D-1[i][j],边
的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。
迭代:设Dk-1已求出，如何得到Dk(0?k?n-1)
Dk-1[i][j]表示从i到j的中间点不大于k-1的最短路径p:i„j，
考虑将顶点k加入路径p得到顶点序列q:i„k„j，
若q不是路径，则当前的最短路径仍是上一步结果:Dk[i][j]= Dk,1[i][j];
否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。
因为q的两条子路径i„k和k„j皆是中间点不大于k,1的最短路径，所以从i到j中间点不大于k的最短路径长度为:
Dk[i][j],min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }
二、 利用图论知识寻找指定两点最短路径 2.1 把实际问题转化成图论问题
图1 重庆邮电大学地图
上图为邮电大学的地图，我们在地图中选取重邮的八个地方看成是八个点(1、新世纪超市 2、三教学楼 3、数字图
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
馆 4、二教学楼 5、信科大楼 6、太极操场 7、老图书馆 8、31栋宿舍)，用线段把每一个点与其相邻的点连接起
来，从而形成一个无向图。再根据实际情况:不同地点的距离问题;路的畅通与
否等给相应的边赋上权值，最后得出一个赋权图，如图2:
图2 赋权图
2.2 Floyd算法用C++实现
#include
#include
#include
using namespace std;
#define MAX_VEX_NUM 10
vector allPath; //向量，用来存放所有的顶点a到顶点i的路径 vector all; //向量，用来存放对应路径的长度 struct MGraph
{
char vexs[MAX_VEX_NUM];
int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
int vexnum,arcnum;
};
MGraph G;
int Locatevex(MGraph G,char v)//图的基本操作，寻找V的位置 {
int i=0;
while(i>G.vexnum>>G.arcnum;
cout<<"请输入顶点的名称(0--9)"<>G.vexs[i];
for(int q=0;q>v1>>v2>>weight;
int a=Locatevex(G,v1);
int b=Locatevex(G,v2);
G.arcs[a][b]=weight;
G.arcs[b][a]=G.arcs[a][b];
}
cout<<"该图的邻接矩阵表示为:\n";
for(int n=0;n"+vexs;
allPath.push_back(path);
all.push_back(Long);
cout<<"路径:"<"+vexs;
int i=Locatevex(G,vexs);
visited[i]=true;
for(int j=0;j>va;
cout<<"请输入您想到达的位置:";
cin>>vb;
cout<
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
。
参考文献:
[1]殷剑宏、吴亚开.图论及其算法[M].合肥:中国科学技术大学出版社,2005 [2]严蔚敏.数据结构(c语言版)[M].北京:清华大学出版社,2009
浙公网安备 33021202002483