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

最短路径算法应用
─校园导游咨询
摘要:据调查,现在随着人们的收入提高和对物质生活以外的追求,外出旅游的人数逐年增加。但是由于假期时间一般很短,所以人们就像用最少的时间参观看完尽量多的景点。这就用到了图论中的一些知识,图论中的最短路算法显得越来越重要,在实际的旅行中,人们总是希望能找到一个最短最有效的路径可以参观所有的景点,在一个大的景区内部同样如此。
本文运用了图论中的最短路径算法,邻接矩阵,赋权图等知识,针对我校暨重庆邮电大学内的几处标志性建筑的遍历为基础,建模了赋权图,模拟了在任意两点之间的最短路径的实现以及编程显示。
关键词:数据结构;最短路径;迪杰斯特拉算法;
一:背景及意义
设计你的学校的校园平面图,所含景点不少于8个(中心食堂、信科、图书馆……)
⑴为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。
⑵为来访客人提供任意景点相关信息的查询。测试数据:由读者根据实际情况指定。
⑶在社会生活中,最短距离的运用相当广泛。除了该课题中校园导游咨询外,还有于此相关的城市道路的设计,交通线路的设计,旅游景点的设计等等。除了路径长度方面外,到两地花费的最少、时间的最短等等都是同样的道理。
二:涉及的图论知识
在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0, v1,……, vk)的权是指其组成边的所有权值之和:
定义u到v间最短路径的权为
从结点u到结点v的最短路径定义为权的任何路径。①
边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。
单目标最短路径问题: 找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向,我们就可以把这一问题转化为单源最短路径问题。
单对结点间的最短路径问题:对于某给定结点u和v,找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题,则这一问题也就获得了解决。对于该问题的最坏情况,从渐进意义上看,目前还未发现比最好的单源算法更快的方法。
每对结点间的最短路径问题:对于每对结点u和v,找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。
在某些单源最短路问题中,可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路,则对所有,最短路径的权的定义依然正确①。即使它是一个负值也是如此。但如果存在一从s可达的负权回路,最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径
——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径,因此如果从s到v的某路径中存在一负权回路,我们定义。
图1 含有负权和负权回路的图
图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在一条路径(路径<s,a>),所以:。
类似地,从s到b也只有一条通路,所以:
。①
从s到c则存在无数条路径:<s,c>,<s,c,d,c>,<s,c,d,c,c,d,c>等等。因为回路<c,d,c>的权为6+(-3)=3>0,所以从s到c的最短路径为<s,c>,其权为:
。
类似地,从s到d的最短路径为