注释:其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。
正文:
GIS 领域最短路径搜索问题的一种高效实现
摘 要 目前在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 最短路径搜索算法的优化途径
2 原始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 算法的搜索过程, 可近似为以源点和终点为焦点的一系列同心椭圆. 因为永久标
此主题相关图片如下：
记点的选取原则为: 当前结点距源点的最短距离与此结点到终点的直线距离之和最小者被选取为永久标记点, 所以其搜索过程明显趋向于终点, 搜索过程到达终点的速度明显快于原始D ijk st ra 算法, 搜索到的结点少于原始D ijk st ra 算法.如图1 (b) 所示, 设S p = 2, S q= 5, p E = 8, qE =2. 从源点出发进行原始D ijk st ra 算法搜索, 首先选取结点p 和q 作为临时标记点, 因为S p 长度小于S q 长度, 所以选取结点p 为永久标记结点, 再以p为新的源点继续进行下一轮搜索, 而结点p 则是最后要被淘汰的. 如果采用直线优化D ijk st ra 算法, 则因为S p + p E = 10, S q+ qE = 7, 所以结点q 被选取为永久标记点. 如图2 所示,L 1 为临时标记结点P 1距源点的最短路径长度, L n 为临时标记结点P n 距源点的最短路径长度,D 1 为结点P 1 到终点的直线距离,D n 为结点P n 到终点的直线距离, P 1 和P n 的连线为C. 原始D ijk st ra 算法永久标记结点的选取原则是: 如果L 1> L n , 则选取P n 为永久标记结点,如果L 1< L n , 则选取P 1 为永久标记点. 直线优化D ijk st ra 算法永久标记点的选取原则是: 如果L 1+D 1> L n+ D n , 则选取P n 为永久标记结点, 如果L 1+D 1< L n+ D n , 则选取P 1 为永久标记结点.
此主题相关图片如下：
直线优化D ijk st ra 算法永久标记结点选取原则
的一个前提条件是L 1 为P 1 到源点的最短路径, 即
P 1 的最短路径值不会再被修改, 也即
已知: L 1+ D 1< L n+ D n 证明: L n+ C> L 1
因为 L n+ D n> L 1+ D 1
所以 L n+ D n- D 1> L 1
又因为 CE D n- D 1
所以 L n+ C> L 1 证毕.
直线优化D ijk st ra 算法特别适合于网络中弧的权值为弧长度, 并且可以认为整个网络在同一平面内. 在地理信息系统中, 一般在较小的地理范围内,可以用平面代替地球表面; 网络中两结点间的直线距离最短是此优化算法的另外一个前提条件.
直线优化D ijk st ra 算法优于原始D ijk st ra 算法的关键在于其最大搜索范围得到了明显的减小, 从而使搜索速度得到提高, 图3 显示了两种算法的最大搜索范围. 图中圆为原始D ijk st ra 算法的最大搜索范围, 椭圆为直线优化D ijk st ra 算法的最大搜索
范围.
此主题相关图片如下：
设最短路径长度为2a, 则原始D ijk st ra 算法的最大搜索圆半径极限为2a, 直线优化D ijk st ra 算法的最大搜索椭圆长轴长度为2a, 椭圆上一点到两个焦点的直线距离之和为2a, 设其短轴长度为2b, 源点和终点为焦点. 用圆和椭圆的面积来近似表示两
种算法所搜索的结点数目, 其分别为
此主题相关图片如下：
索范围的4倍以上, 表1 中的数据进一步证明了这一点.直线优化D ijk st ra 算法最大搜索范围与源点在网络中的位置有关. 当源点接近网络边界或者处在
此主题相关图片如下：
网络边界上时, 其搜索的结点数目可能不会明显地少于原始D ijk st ra 算法的. 总之, 直线优化D ijk st ra算法搜索的结点数目要比原始D ijk st ra 算法少, 具体的数量根据网络的具体情况不同而有所差异. 另外, 当源点和终点不连通时, 两种算法的搜索范围是相同的, 它们的搜索终止条件都是搜索到整个网络所有与源点连通的结点而未找到终点. 在这种情况下, 直线优化D ijk st ra 算法与原始D ijk st ra 算法搜索的结点数相同, 但直线优化D ijk st ra 算法的开销要高于原始D ijk st ra 算法, 因为直线优化D ijk st ra算法要处理两结点间的最短距离计算问题.
1. 3 最短路径搜索算法的选取
根据对原始D ijk st ra 算法优化方法的论述可知, 其优化途径有两个: 一是对临时标记结点进行排序, 二是减小永久标记结点的数量.对临时标记结点的排序选取堆排序方法[ 8 ] , 将结点最短路径值作为堆排序的关键字, 采用堆排序
有如下考虑:
(1) 充分利用了现有堆数据, 大大降低了数据比较的频率. 堆排序的主要运行时间消耗在建初始堆上, 而对于D ijk st ra 算法来说, 整个最短路径的搜索过程中进行的n 次堆排序只需要建一个堆, 从而明显克服了堆排序的主要缺点, 使堆排序的优势更加明显地发挥出来.
( 2)D ijk st ra 算法中结点最短路径值的修改总是比原来的值小. D ijk st ra 算法中采用小根堆即堆顶元素为关键字值最小的元素. 堆中某元素的关键字(即结点的最短路径值) 修改后, 进行堆的重新整理操作时, 只需要判断此元素是否需要和其父结点进行位置调整. 所以D ijk st ra 算法中堆的重新整理操作要比传统堆的重新整理过程简单、高效.
(3) 堆排序只需要一个记录大小的辅助空间. 快速排序需要O ( logn) 的辅助存储空间, 而归并排序则需要O (n) 的辅助存储空间.
基于以上的讨论, 对原始D ijk st ra 算法(算法1 )、堆优化D ijk st ra 算法( 算法2 )、直线优化D ijk st ra 算法( 算法3 )、堆优化结合直线优化D ijk st ra 算法(算法4) 的速度测试结果如表2.
此主题相关图片如下：
实验数据采用全国1∶1 000 000 公路网, 共有22 320 个结点, 55 772 个弧段.操作系统:W indow s 2000 P rofessional.硬件设备: CPU : In tel Pen t ium MMX200, 内存: 128M , 硬盘: 614G.最短路径搜索算法采用堆排序结合直线优化D ijk st ra 算法; 临时标记结点采用堆来存储; 永久标记结点的搜索采用直线优化D ijk st ra 算法, 可进而达到从两个方面分别对D ijk st ra 算法进行优化的目的.
1. 4 数据存储结构
最短路径搜索问题一般都采用结点2弧结构的存储结构表示. 这一方面清晰地表达了网络的拓扑结构, 另一方面更加便于D ijk st ra 算法的实现. 根据堆优化结合直线优化D ijk st ra 算法的特点, 设计的数据
结构如图4 所示.
此主题相关图片如下：
以下对数据结构进行简单的描述:
(1) 网络结点数据结构说明(Po in tReco rd)
A rc Index: 以此结点为起点的第1 个弧在弧数
组中的下标
L at itude: 结点纬度
Longitude: 结点经度
(2) 弧数据结构说明(A rcReco rd)
F irstNode: 弧的起点编号
EndNode: 弧的终点编号
L ength: 弧的长度
IndexGraph ics: 此弧在网络数组中的索引(网
络数组下标)
(3) 弧描述点数据结构说明(Po in t) (包括弧结
点在内的整个弧的描述点)
L at itude: 结点纬度
Longitude: 结点经度
(4) 网络数据结构说明(Graph icReco rd) :
Coun tPo in t: 弧的结点个数
A rcPo in t: 结点数组指针
(5) 最短路径结点数据结构说明
(D ijk st raPo in t)
Heap ID: 此结点在堆中的编号
P reNode: 最短路径中此结点的前一结点
Sho rtestL en: 源点到此结点的最短路径长度由图4 可见, 此数据结构完全是为最短路径搜索算法量身定制的. 其能够提高效率的最突出一点是: 网络结点数据结构存储了以此结点为起点的第1 个弧的数组下标, 这样就不需要遍历整个弧数组来搜索以此结点为起点的弧; 此外, 弧数组中各个弧的信息, 以弧的起始结点为关键字排序存储, 所以起始结点相同的弧是连续存储的, 这种结构极大方便了查找某一结点的所有连通结点. 此数据结构的其他环节都按照这样的指导思想设计, 使算法实现起来更加流畅.最短路径结点数据结构为最短路径搜索算法中使用的结点数据结构. 网络结点数据结构、弧数据结构和网络数据结构联合构成整个网络描述结构. 在全国主要城市间公路信息查询系统的开发中, 最短路径结点数据是每个客户请求线程都需要建立的数据结构. 整个网络的描述结构只在服务器响应第1个客户的请求时建立, 并存储在应用程序的数据堆中, 其他客户的请求虽然都需要访问此数据, 但不需要重新建立整个拓扑网络的描述数据.最短路径搜索数据文件. 文件结构描述如表3所示.
此主题相关图片如下：
2 应用实例应用于全国主要城市间公路信息查询系统, 采用的最短路径搜索算法是: 堆排序优化算法与直线优化D ijk st ra 算法的结合, 这样系统响应速度明显快于系统采用原始D ijk st ra 算法的响应速度, 取得了较为满意的效果. 系统运行界面如图5 所示.
此主题相关图片如下：
此系统在网络带宽为56K 的环境下运行, 除了
第1 次访问本系统稍有延迟外, 用户进行各个城市
间的最短路径查询操作感觉不到此系统的延迟.
3 结 论
直线优化D ijk st ra 算法是在平面条件下进行的优化, 从算法的速度、资源消耗和稳定性3 方面综合考虑, 是目前了解的各种D ijk st ra 最短路径搜索优化算法中较优秀的一个. 其适用的网络应具有以下
特征:
(1) 网络可以近视为平面网络.
(2) 具有确定的空间位置.
(3) 弧的权值为弧的长度.
而堆排序优化D ijk st ra 算法则适合各种特征的网络. 原始D ijk st ra 算法要求网络弧的权值为非负数, 堆排序优化D ijk st ra 算法和直线优化D ijk st ra算法当然也要遵循原始D ijk st ra 算法的要求.地理信息系统中最短路径搜索功能的实现还需要根据不同应用领域的具体特征进行改进和优化,例如铁路领域的最短路径搜索问题等. 除了实现过程中在数据结构和算法上要周密考虑, 其他每一个细节问题也要根据具体情况采用效果最好的实现方法或者技术, 才可以开发出综合性能很好的最短路径搜索功能模块. 在具体编程中优化处理了许多细节问题, 这些细节对整个系统的性能提高同样起到了推动作用.目前地理信息系统中最短路径搜索的一些串行算法研究(包括本文的研究) 已经取得了比较满意的效果, 因此, 进一步可以考虑进行并行计算的研究,以取得更大的突破.此外, 还要考虑网络中弧的权值问题. 一方面,弧的权值可能不只是弧的长度, 根据具体应用不同还需要考虑其他因素; 另一方面, 弧的权值可能根据时间等参数的变化而变化, 即权值是实时更新的, 全国主要城市间公路信息查询系统在开发过程中考虑了弧的权值问题, 开发了相应的接口.
全文引用