最短路径算法分析及其在公交查询的应用

《最短路径算法分析及其在公交查询的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2001年工程图学学报2001第3期JOURNALOFENGINEERINGGRAPHICSNo.3最短路径算法分析及其在公交查询的应用陈箫枫蔡秀云唐德强华南理工大学广州510641摘要通过对常见的最短路径及其算法的分析指出以往的最短路径算法不能实现公交路线的查询提出更适合公交查询的最短路径算法以及广州市公交线路查询系统的实现关键词最短路径公交查询中图分类号TB23文献标识码A文章编号1003-0158(2001)03-0020-051常见的最短路径问题及算法1.1在实际中常见的最短路径问题例如如果司机用汽车运输货物从A城到B城他就会考虑

2、走路程最短或者时间最少的道路这是考虑路程或时间的最短路径问题又例如要在A地到B地之间铺设煤气管道在AB地间的长方形地区划分格子点根据地形土壤是否经过江河泥塘农田村庄郊区城镇公路铁路等各种情况将从一格子点至另一格子点的铺设费用估计出来求由A地到B地铺设煤气管道经过哪些格子点使总的造价最小这是考虑费用的最短路径问题另外在线路安排设备更新厂区布局城市规划电子导航交通转车等方面均需要考虑到最短路径问题1.2赋权图的最短路径设有图G对G中的每一条边ViVj相应地有一个数LViVj称为边的权图G连同在它边上的权被称为赋权图一条边的权也说成它的长一条道

3、路u=V1V2Vn的长是u上所有长的和即LV1V2+LV2V3++LVn-1Vn在赋权图中给定一个始点Vi及终点Vj所谓最短路径问题就是在ViVj道路集合{Pij}中寻求长为最小的路径这样的路径称为从Vi到Vj的最短路径从Vi到Vj的最短路径长度即最短距离记作dViVj赋权图中的权可以表示两个顶点间的距离或者途中所经的时间或者交通费用等此时路径长度的度量不是路径上边的数目而是路径上边的权距离时间费用等之和收稿日期2001-03-06作者简介陈箫枫1974-男广西浦壮人硕士研究生主要研究领域为计算机图形学第3期陈箫枫等最短路径算法分析及其在

4、公交查询的应用21例如图1每个顶点表示城市两个顶点构成的边表示两城市间的道路边上的数字也就是上面说的权表示两个城市之间的距离公里如果用汽车运输货物从A城到H城司机就会考虑走路程最短的道路那么最短路径是哪一条呢应该是ABDH而且最短距离dAH=LAB+LBD+LDH=100+100+100=300公里1.3迪杰斯特拉(Dijkstra)最短路径算法寻找两顶点间的最短路径的算法很多目前公认最好的算法是迪杰斯特拉Dijkstra在1959年提出的它不仅求出从始点到终点的最短路径而且最后所得到的实际上是始点到各顶点的最短路径对Dijkstra算法

5、进行补充得出的步骤如下第一步初始化V={12N}S={F}D[I]=L[FI]Y[I]=F其中I=12NF表示路径的始点I表示某一顶点N表示网络中所有顶点的数目V是所有顶点的集合L[FI]表示从F点到I点的距离S是顶点的集合D为N个元素的数组用来存储顶点F到其它顶点的最短距离Y为N个元素的数组用来存储最短路径中在顶点I之前经过的最近顶点第二步从VS集合中找一个顶点T使得D[T]是最小值并将T加入到S集合中如果VS是空集合则结束运算第三步调整YD数组中的值在VS集合中对于顶点T的邻接各顶点I如果D[I]>D[T]+L[IT]那么令Y[I]=

6、TD[I]=D[T]+L[IT]继续执行第二步2公交线路的最短路径算法2.1复杂公交线路查询不能采用Dijkstra最短路径算法Dijkstra最短路径算法由于其稳定性能适应网络拓扑的变化同时对系统的内存空间占用少因而在计算机网络拓扑路径选择以及GIS中得到广泛的应用但是对公交线路来说Dijkstra算法所采用的数据结构及其实现方法总体上说是比较复杂的其缺点也是明显的难以应付公交线路的网络拓扑中的复杂性主要表现如下1数据结构复杂网络在教学和计算领域被抽象为图所以其基础是图的存储表示一般而言无向图可以用邻接矩阵和十字链表表示公交线路网络拓扑

7、很难用现有的数据结构加以完整的表示如果采用现有的最短路径算法分析其建立的公交线路网络图的数据结构模型将非常复杂2算法时间长以Dijkstra算法来计算公交路线最短路径在大数据量的情况下计算速度会慢得让人难以忍受系统设计中要求公交转车的查询必须在较短的时间内完成Dijkstra算法难以实现3Dijkstra最短路径算法对于网络拓扑图要求简捷对于复杂的广州公交网络拓扑必须对其进行复杂的抽象合并成简捷的网络拓扑图这无疑增加了程序的复杂性22工程图学学报2001年4公交转车中的特殊性并不一定要求用Dijkstra算法算出一条最短路径求乘客从A站到

8、B站的最短路径将每个公交站点均看作网络上的顶点每相邻站点间的路段看作一条边假设乘客每到一个公交站点都考虑转车才可用Dijkstra算法计算最短路径用Dijkstra算法计算出来的结果可能是从A