欢迎来到天天文库
浏览记录
ID:19636059
大小:103.40 KB
页数:8页
时间:2018-10-04
《论文格式 - 副本2new》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、2011年秋季学期《图论》课程论文姓名:潘玉军学院:理学院学号:1001014243年级:2010级专业:数学与应用数学班级:2班8图论中最短路算法及其应用潘玉军(佳木斯大学理学院数学系,黑龙江佳木斯154007)摘要:随着旅行人数的增加以及节约时间的需要,图论中的最短路算法显得越来越重要,在实际的旅行中,对几个地点的遍历中,人们总是希望能找到一个最短最有效的路径可以遍历所有的景点,在一个大的景点内部同样如此。本文运用了图论中的最短路径算法,邻接矩阵,赋权图等知识,针对我校暨佳木斯大学内的几处标志性建
2、筑的遍历为基础,建模了赋权图,模拟了在任意两点之间的最短路径的实现以及编程显示。关键词:图论;最短路径;Dijkstra算法;计算路径和一:需求分析本论文主要实现查询我校任意两点之间的最短路径,以我校方位布局为根据,首先要对我校的布局有所了解,然后估计出主要建筑物的距离。数学建模,运用图论知识进行解决。此方法可用于多数别的地方,如景点的查询,旅行路线的查询等。实际应用非常广泛。二:运用图论基本知识在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权函数W:ER为从边到实型权值的映射。路
3、径P=(v0,v1,……,vk)的权是指其组成边的所有权值之和:定义u到v间最短路径的权为从结点u到结点v的最短路径定义为权的任何路径。[1]边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。单目标最短路径问题:找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向,我们就可以把这一问题转化为单源最短路径问题。8单对结点间的最短路径问题:对于某给定结点u和v,找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题
4、,则这一问题也就获得了解决。对于该问题的最坏情况,从渐进意义上看,目前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题:对于每对结点u和v,找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。在某些单源最短路问题中,可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路,则对所有,最短路径的权的定义依然正确[1]。即使它是一个负值也是如此。但如果存在一从s可达的负权回路,最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径——因为我们总可
5、以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径,因此如果从s到v的某路径中存在一负权回路,我们定义。图1含有负权和负权回路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在一条路径(路径),所以:。类似地,从s到b也只有一条通路,所以:。[1]从s到c则存在无数条路径:,,等等。因为回路的权为6+(-3)=3>0,所以从s到c的最短路径为6、>,其权为:。类似地,从s到d的最短路径为,其权为:。[2]8同样,从s到e存在无数条路径:,,等等.由于回路的权为3+(-6)=-3<0,所以从s到e没有最短路径。只要穿越负权回路任意次,我们就可以发现从s到e的路径可以有任意小的负权值,所以:类似地,[2]因为g是从f可达的结点,我们从s到g的路径可以有任意小的负权值,则:。结点h,j,i也形成一权值为负的回路,但因为它们从s不可达,因此。[2]一些最短路径的算法,例7、如Dijkstra算法,都假定输入图中所有边的权取非负数,如公路地图实例。另外一些最短路算法,如Bellman-Ford算法,允许输入图中存在权为负的边,只要不存在从源点可达的权为负的回路,这些算法都能给出正确的解答[3]。特定地说,如果存在这样一个权为负的回路,这些算法可以检测出这种回路的存在。三:数学建模本论文着手解决实例为我校情况,主要抽象出了以下八个典型的地点:大学东门,理学院,U型楼,图书馆,主楼,新食堂,机械院,材料院。以下为我校平面图:大学东门图书馆主楼新食堂机械院材料理院U型楼60108、01207050602080406050308图2我校主要建筑分布图运用图论知识对上图进行邻接矩阵的表示,为了表示方便我对上图的地点:大学东门,理学院,U型楼,图书馆,主楼,新食堂,机械院,材料院。分别由数字1,2,3,4,5,6,7,8代表。123456781∞50∞6070∞∞∞250∞120∞40∞∞∞3∞120∞∞∞60∞∞460∞∞∞20∞80∞57040∞20∞5060∞6∞∞60∞50∞100∞7∞∞∞8060100∞308∞∞∞∞∞∞30
6、>,其权为:。类似地,从s到d的最短路径为,其权为:。[2]8同样,从s到e存在无数条路径:,,等等.由于回路的权为3+(-6)=-3<0,所以从s到e没有最短路径。只要穿越负权回路任意次,我们就可以发现从s到e的路径可以有任意小的负权值,所以:类似地,[2]因为g是从f可达的结点,我们从s到g的路径可以有任意小的负权值,则:。结点h,j,i也形成一权值为负的回路,但因为它们从s不可达,因此。[2]一些最短路径的算法,例
7、如Dijkstra算法,都假定输入图中所有边的权取非负数,如公路地图实例。另外一些最短路算法,如Bellman-Ford算法,允许输入图中存在权为负的边,只要不存在从源点可达的权为负的回路,这些算法都能给出正确的解答[3]。特定地说,如果存在这样一个权为负的回路,这些算法可以检测出这种回路的存在。三:数学建模本论文着手解决实例为我校情况,主要抽象出了以下八个典型的地点:大学东门,理学院,U型楼,图书馆,主楼,新食堂,机械院,材料院。以下为我校平面图:大学东门图书馆主楼新食堂机械院材料理院U型楼6010
8、01207050602080406050308图2我校主要建筑分布图运用图论知识对上图进行邻接矩阵的表示,为了表示方便我对上图的地点:大学东门,理学院,U型楼,图书馆,主楼,新食堂,机械院,材料院。分别由数字1,2,3,4,5,6,7,8代表。123456781∞50∞6070∞∞∞250∞120∞40∞∞∞3∞120∞∞∞60∞∞460∞∞∞20∞80∞57040∞20∞5060∞6∞∞60∞50∞100∞7∞∞∞8060100∞308∞∞∞∞∞∞30
此文档下载收益归作者所有