摘 要 目前在GIS 领域, 对最短路径搜索问题的研究和应用较多, 其中最短路径搜索算法的效率问题是普遍关
注和在实际应用中迫切需要解决的问题. 通过对基于D ijk st ra 最短路径搜索算法的优化途径的分析, 从算法本身
和数据存储结构两个方面同时对此问题的解决方案进行了优化, 提出了直线优化D ijk st ra 算法, 并进行了必要的
证明和适用条件论述. 此方案应用到“全国主要城市间公路信息查询”系统中, 取得了较为满意的效果, 同时也给出
了相关的测试数据.
关键词 地理信息系统(420·3040) D ijk st ra 最短路径
中图法分类号: TP391. 41 文献标识码: A 文章编号: 100628961 (2003) 0820951206
0 引 言
近些年来, 地理信息系统(G IS) 在交通、公安、
土地资源管理、城市规划等方面都得到了广泛且深
入的应用. 这些应用领域中的地理信息系统经常涉
及最短路径搜索问题, 例如城市公交系统的最短路
径搜索系统, 公安系统的紧急出警和救助系统、城市
供水、供电、供气管线的规划设计系统等. 本文只讨
论一般公路交通网络中两结点间的最短路径搜索问
题, 其他相关的问题, 如中国邮路问题等虽在实际应用中也有较大的需求, 但暂不列入本文的讨论范围.
目前基于地理信息系统的最短路径搜索算法研
究很多[ 1～ 7 ] , 其中1959 年迪克斯特拉(D ijk st ra) 提
出的单源问题算法是最适合拓扑网络中两结点间最
短路径搜索的算法之一, 本文将此算法称为“原始
D ijk st ra 算法”[ 8, 9 ]. 后人在此算法的基础上进行了
大量的优化[ 1～ 9 ] , 本文在原始D ijk st ra 算法的基础
上, 从核心算法和数据存储结构两方面进行了改进,
并应用到基于W ebG IS 的“全国主要城市间公路信
息查询系统”, 通过实际测试, 速度和内存消耗两项
指标都取得了比较满意的效果.
1 GIS 领域最短路径搜索算法的高效
实现
1. 1 最短路径搜索算法的优化途径
原始D ijk st ra 算法将网络结点分为未标记结
点、临时标记结点和永久标记结点3 种类型. 网络中
所有结点首先初始化为未标记结点, 在搜索过程中
和最短路径结点相连通的结点为临时标记结点, 每
一次循环都是从临时标记结点中搜索距源点路径长
度最短的结点作为永久标记结点, 直至找到目标结
点或者所有结点都成为永久标记结点才结束算法.
在原始D ijk st ra 算法中, 临时标记结点无序地
存储在无序表中, 这无疑成为D ijk st ra 算法的瓶颈,
因为每次在临时标记点中搜索路径最短的结点时,
都要遍历所有的临时标记结点. 解决的办法就是将
临时标记结点按照最短路径排序, 每个搜索过程不
必全部遍历或者只较少地遍历临时标记点, 这也是
目前各种基于原始D ijk st ra 算法的各种优化算法的
重要出发点之一; 另外一个优化途径是尽量减少最
短路径分析过程中搜索的临时结点数量, 从而尽快
到达目标结点.
1. 2 直线优化D ijkstra 算法
原始D ijk st ra 算法一种行之有效的优化方法
是: 减小算法中成功搜索的搜索范围, 以尽快到达目
标结点. 其核心思想是: 在所研究的网络可以被看成
平面网络的条件下, 将临时标记结点到源点的最短
路径与本临时标记结点到目标结点的直线距离之和
作为此临时标记结点的一个属性值, 这个属性值将
作为从临时标记结点集合中选取永久标记结点的依
据, 即选取此属性值最小的临时结点作为永久标记
结点, 这种优化方法称为直线优化D ijk st ra 算法. 此
方法使得D ijk st ra 算法的搜索方向智能地趋向于目
标结点, 减少了算法中遍历的结点个数, 从而提高了
搜索速度.
直线优化D ijk st ra 算法与原始D ijk st ra 算法的
搜索过程比较示意图如图1 所示.
由图1 可见, 原始D ijk st ra 算法的搜索过程, 可
近似为以源点为圆心的一系列同心圆, 搜索过程没
有考虑终点所在的方向或位置, 在从源点出发的搜
索过程中, 其他结点与终点被搜索到的概率是相同
的; 直线优化D ijk st ra 算法的搜索过程, 可近似为以
源点和终点为焦点的一系列同心椭圆. 因为永久标
...............................