图论中最短路算法及其应用.doc

图论中最短路算法及其应用 摘要：随着旅行人数的增加以及节约时间的需要，图论中的最短路算法显得越来越重要，在实际的旅行中，对几个地点的遍历中，人们总是希望能找到一个最短最有效的路径可以遍历所有的景点，在一个大的景点内部同样如此。 本文运用了图论中的最短路径算法，邻接矩阵，赋权图等知识，针对我校暨重庆邮电大学内的几处标志性建筑的遍历为基础，建模了赋权图，模拟了在任意两点之间的最短路径的实现以及编程显示。 关键词：图论；最短路径；迪克斯屈拉算法；计算路径和 一：需求分析 本论文主要实现查询我校任意两点之间的最短路径，以我校方位布局为根据，首先要对我校的布局有所了解，然后估计出主要建筑物的距离。数学建模，运用图论知识进行解决。 此方法可用于多数别的地方，如景点的查询，旅行路线的查询等。实际应用非常广泛。 二：运用图论基本知识 在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0, v1,……, vk)的权是指其组成边的所有权值之和： 定义u到v间最短路径的权为 从结点u到结点v的最短路径定义为权的任何路径。[1] 边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。 单目标最短路径问题： 找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u和v，找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。 每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。 在某些单源最短路问题中，可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路，则对所有，最短路径的权的定义依然正确[1]。即使它是一个负值也是如此。但如果存在一从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径，因此如果从s到v的某路径中存在一负权回路，我们定义。 图1 含有负权和负权回路的图 图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在一条路径(路径s,a)，所以：。 类似地，从s到b也只有一条通路，所以： 。[1] 从s到c则存在无数条路径：s,c,s,c,d,c,s,c,d,c,c,d,c等等。因为回路c,d,c的权为6+(-3)=30，所以从s到c的最短路径为s,c，其权为： 。 类似地，从s到d的最短路径为s,c,d，其权为： 。[2] 同样，从s到e存在无数条路径：s,e,s,e,f,e,s,e,f,e,f,e等等.由于回路e,f,e的权为3+(-6)=-30，所以从s到e没有最短路径。只要穿越负权回路任意次，我们就可以发现从s到e的路径可以有任意小的负权值，所以： 类似地， [2] 因为g是从f可达的结点，我们从s到g的路径可以有任意小的负权值，则： 。 结点h，j，i也形成一权值为负的回路，但因为它们从s不可达，因此 。[2] 一些最短路径的算法，例如Dijkstra算法，都假定输入图中所有边的权取非负数，如公路地图实例。另外一些最短路算法，如Bellman-Ford算法，允许输入图中存在权为负的边，只要不存在从源点可达的权为负的回路，这些算法都能给出正确的解答[3]。特定地说，如果存在这样一个权为负的回路，这些算法可以检测出这种回路的存在。 三：数学建模 本论文着手解决实例为我校情况，主要抽象出了以下八个典型的地点：老校大门，信科大厦，三十三幢学生公寓，数字图书馆，二教学楼，中心食堂，三教学楼，移通学院。 以下为我校平面图： 图2 我校主要建筑分布图 运用图论知识对上图进行邻接矩阵的表示，为了表示方便我对上图的地点：老校大门，信科大厦，三十三幢学生公寓，数字图书馆，二教学楼，中心食堂，三教学楼，移通学院。分别由数字1，2，3，4，5，6，7，8代表。 1 2 3 4 5 6 7 8 1 ∞ 50 ∞ 60 70 ∞ ∞ ∞ 2 50 ∞ 120 ∞ 40 ∞ ∞ ∞ 3 ∞ 120 ∞ ∞ ∞ 60 ∞ ∞ 4 60 ∞ ∞ ∞ 20 ∞ 80 ∞ 5 70 40 ∞ 20 ∞ 50 60 ∞ 6 ∞ ∞ 60 ∞ 50 ∞ 100 ∞ 7 ∞ ∞ ∞ 80 60 100 ∞ 30 8 ∞ ∞ ∞ ∞ ∞ ∞ 30 ∞ 表1：我校建筑抽象图