（地图学与地理信息系统专业论文）gis中最短路径问题的研究与实现.pdf

g i s 中最短路径问题的研究与实现 摘要 地理信息系统( g i s ) 自二十世纪六十年代开始发展至今，已经逐渐成为一 门成熟的技术，其在交通、旅游、环境等诸多领域的应用使地理信息系统被越 来越多的用户所接受，成为人们工作、生活中一个强有力的工具。 最短路径问题是地理信息系统网络分析中的一个关键内容，目前在g i s 中， 特别是在交通、电力等g i s 应用系统中，最短路径算法的优化和实现已经成为 整个系统的核心功能之一。因此，研究最短路径算法也成为应用g i s 系统研究 和发展的一个热点。 本文采用目前较为成熟的d i j k s t r a 算法，详细分析了算法实现过程中的时 间消耗和内存消耗。根据a r c g i s 平台下的数据格式，对数据进行预处理；通过 算法效率分析，选择效率较高的邻接多重表；根据算法的搜索方式，通过预先 排序的方式减少搜索时间；引入新的数据类型，保证邻接多重表的重复使用。 最后，本文在a r c g i se n g i n e 平台下优化实现了d i j k s t r a 算法，并对运行结果 进行了分析。 关键词ig i s ，最短路径，a r c g i se n g i n e ，d i j k s t r a g i s 中最短路径问题的研究与实现 a b s t r a c t g e o g r a p h i ci n f o r m a t i o ns y s t e m s ( g i s ) ，w h i c hh a sb e e nd e v e l o p e ds i n c e1 9 6 0 s ， h a sb e c o m eam a t u r et e c h n o l o g y i ti sa c c e p t e di nm o r ea n dm o r es c o p e ss u c ha s t r a f f i c t o u ra n de n v i r o n m e n l i sap o w e r f u lt o o li np e o p l e sw o r ka n dl i f e s h o n e s tp a t hf i n d i n gi sak e yc o n t e n ti nn e t w o r k a n a l y s i so fg i s o p t i m i z i n g a n di m p l e m e n t a t i o nt h ea r i t h m e r l eo fs h o r t e s tp a t hf i n d i n gi so n eo fk e r n e l - f u n o t i o n s i ng i ss y s t e m sn o w , e s p e c i a l l yi nt l a f 矗cg i sa n de l e c t r i c i t yg i s s ot h es t u d vo f a r i t h m e t i co fs h o r t e s tp a t hf i n d i n gi sah o t p o ti ns t u d ya n di m p l e m e n t a t i o no fg i s t h e p a p e r c h o o s e s m a t u r e o i j k s t r a ,a n a l y z e t i m e - c o n s u m ea n d m e m o r y - - c o n s u m em i n u t e l y b a o i lt h ed a t af o r m a ti na r c g i s t h ep a p e rp r e - t r e a t t h ed a t a , c h o o s ee 衔c i e n ta d j a c e n c ym u l t i l i s t , p r e s o r tt h el i s tt oq u i c k e nt h e s e a r c h - p r o c e s s ，i n t r o d u c en e ws t l a l c t u r ei n t ot h ep r o g r a mt ok e e pu pt h ea d j a c e n c y m u l t i l i s t t h ep a p e ri m p l e m e n t st h ea r i t h m e t i ci na r c g i se n g i n ep 1 a f f o r m , a n d a n a l y z e st h er e s u l ta tl a s t k e yw o r d s ：g i s ；s h o r t e s tp a t hf i n d i n g ；a r c g i se n g i n e ；o i j k s 姐 g i s 中最短路径问题的研究与实现 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别 加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同 志的研究成果对本人的启示和所提供的帮助，均己在论文中做了明确的声明并表示谢意。 学位论文作者签名 知侈 日期： 学位论文版权的使用授权书 妇7 。， 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权 保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权辽宁 师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后使用本授权书。 一繇彩坦 指导教师签名： 日期： 岔宝 溯7 g i s 中最短路径问题的研究与实现 第一章研究内容和研究意义 1 1 国内外研究现状 ：g i s 中的最短路径查找问题是g i s 应用中研究的一个重要内容，g i s 中的最 短路径问题相对于单纯的最短路径更具复杂性。由于地理信息数据量巨大，特 别在交通g i s 中，各类道路、路口等元素以及它们所包含的各类属性数据都可 能成为影响最短路径计算的因素。目前有许多国内外的高校、研究机构和大量 的学者在这一方面进行了许多卓有成效的研究。其中，主要是对现有的最短路 径进行改进和优化，并且以d i j k s t r a 算法和斛算法居多。如对d i j k s t r a 算法 的改进主要有：采用三种基于图论的算法( d i j k s t r a 算法、f l o y d 算法和矩阵 算法) 来建立一个实际的地理信息管理系统，在其中寻找任意两点的最短路径， 并在系统中加以实现，同时讨论这几种算法的原理、特点以及时问复杂度。针 对g i s 道路网的特点，武汉大学的张燕提出了一种基于矢量夹角的最短路径搜 索方法，在搜索过程中引入矢量夹角标量值作为搜索因子，提高了最短路径搜 索向终点收敛的速度“7 。针对采用邻接矩阵时的d i j k s t r a 算法实现，中国测绘 科学研究院的张福浩等提出了一种基于d i j k s t r a 算法的优化算法邻接点算 法，该算法充分利用网络拓扑信息中的弧段的连接关系，避免了使用含有大量 无穷值的关联矩阵，使之更适合带有拐向限制设置的最短路径算法和大量节点 的实际数据”。该算法可以节约大量内存，对于节点数比较多的网络，或者带有 拐向限制设置的网络，具有较好的适用性。跟据d i j k s t r a 算法在某些情况下查 找的最短路径并非最优的问题，电子科技大学的赵建宏等提出了一种基于“乘 位加比小”的代价邻接矩阵的新运算，证明了“代价邻接矩阵乘位加比小算法” 的可行性，其结果可实现有向图全局最短寻径，并且对与任何类型的有向图， 都可以准确查找其最短路径”1 。 经过多年的研究，最短路径算法已经达到一个较为成熟的水平，在导航、 路由等对实时性要求较高的场合都得到了大量应用。 g i s 中最短路径问题的研究与实现 1 2 研究内容及意义 目前，随着互联网技术、无线通信技术等的发展，l b s 位置服务、导航和智 能交通等基于g i s 的服务已经越来越广泛，最短路径搜索是其中的核心问题之 一，因此对g i s 系统中最短路径问题的研究，具有重要的现实意义。本文对当 前的g i s 最短路径研究做了进一步的尝试： ( 1 ) 目前国内使用较多的g i s 平台主要是e s r ia r c g i s 和m a p i n f o 等，其 中a r c g i s 的s h a p e f i l e 数据应用十分广泛，但是s h a p e f i l e 数据由于本身缺乏 对拓扑关系的支持，所以在最短路径查找中有一些先天的不足。本文则利用 s h a p e f i l e 可以附带属性数据的特点，间接为s h a p e f i l e 建立简单的拓扑关系， 从而提高程序效率。这为以后在设计最短路径查找系统时，加强对数据本身的 研究，利用数据本身的一些特点提高寻径效率提供了一些思路。 ( 2 ) 最短路径算法经过多年的发展，形成了一套完整的体系，并且以前 的研究也大多集中在算法本身的改进上，本文则着眼于算法在具体平台上实现 过程中对数据结构的优化上，并取得了不错的效果。这也为今后的研究提供了 新的思考方向。 2 g i s 中最短路径问题的研究与实现 第二章地理信息系统 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m s ，简称g i s ) 是一种采集、 存储、管理、分析、显示与应用地理信息的计算机系统，是分析和处理海量数 据的通用技术。它在最近的3 0 多年内取得了惊人的发展，并广泛地应用于资源 调查、环境评估、区域发展规划、公共设施管理、交通安全等领域，成为一个 跨学科、多方向的研究领域。 地理信息系统属于通用信息系统的范畴，但同时有具有自身的一些特殊性， 地理信息系统的核心是地理空间数据库( g e o s p a t i a ld a t a b a s e ) ，包括空间数 据和地理属性数据，以及在此基础上发展而来的各种空间数据的处理和分析方 法。地理信息系统的定义有两层含义。一方面，地理信息系统是- - 1 7 学科，是 描述、存储、分析和输出空间信息相关理论的和方法的- - f 7 新兴交叉学科；另 一方面，地理信息系统是一个技术系统，是以地理空间数据库为基础，采用地 理模型分析方法，适时提供多种空间、动态的地理信息，为地理研究和地理决 策服务的计算机信息技术系统”。 ， g i s 的理论基础主要有二个支撑点，一是地球科学，二是信息科学。前者涉 及地物空间信息及其关系信息的获取、分类模型及语义表示中的理论问题和实 践问题：后者则涉及信息的组织、存储、处理、可视化表示及传输中的理论问题 和实践问题。g i s 的技术基础包括遥感技术、定位技术和信息技术嘲。 地理信息系统具有以下三个方面的特征”： ( 1 ) 具有采集、管理、分析和输出多种空间信息的能力，具有空间性和动态 性： ( 2 ) 以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间 分析、多要素综合分析和动态预测能力，提供高层次的地理信息； ( 3 ) 由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规或 专门的地理分析方法，作用于空间数据，产生有用信息。 从外部看来。地理信息系统表现为计算机软硬件系统，而其内涵是由计算 机程序和地理数据组成的地理空间信息模型，是一个逻辑缩小的、高度信息化 的地理系统m 。 3 g i s 中最短路径问题的研究与实现 第三章数据结构及算法 图论是数据结构研究中的一个重要内容，也是计算机以及信息科学中的一 个重要研究工具，它最早产生于瑞士数学家欧拉对图的连通性的研究，但是直 到2 0 世纪计算机技术产生之后，图论才得到进一步的研究和发展。最短路径问 题是图论中研究的一个重要方面，在计算机网络、信息、人工智能等领域都有 重要的应用。在g i s 中，最短路径的研究和实现占有很重要的地位。 3 1 关于数据结构、算法和图论中的一些重要定义 时何复杂度：这是算法的时间量度。算法好坏优劣的衡量，最重要的指标 之一是算法程序在计算机上执行的效率，也就是程序运行所消耗的时间。度量 一个程序执行的时间通常有两种方式，一是事后统计，也就是在算法程序开始 运行的同时开始计时，程序运行完成后停止计时，从而获得程序运行时间。这 种方法的好处是直观，并且通过计算机系统的计时器来计时，可以得到相当精 确的时间，缺点是必须完整运行算法程序，对于一个计算量巨大的程序，比如 演示6 4 级汉诺塔，其计算规模十分巨大，即使以当今速度最快的计算机来计算， 计算时间也将以年来计算，所以这种方式基本没有可行性。另外由于计算机软、 硬件环境的不同，导致不能正确的体现算法的好坏。因此常常采用另一种事前 估算方法。事前估算法需要考虑算法策略、所要求解问题的规模、程序编写语 言以及机器指令速度等因素，因此事前估算的方法实际上也不能绝对正确的反 映一个算法的好坏。为了比较同一问题不同算法的好坏，人们引入了一个“运 行工作量”的概念，这个工作量与程序的运行环境无关，而只是依赖于问题的 规模，通常用整数n 的函数来表示工作量，例如： v o i df u n c l ( i n tn ) f o r ( i n ti n d e x l = 0 ：i n d e x l n ；i n d e x l 抖) f o r ( i n ti n d e x 2 = 0 ：i n d e x 2 v e ( 假设v s 、v m 、v e 分别为起点， 中间点和终点) ，假设v m 不在集合s 中，则说明路径v s 一 v 是起点v s 到终点 v m 的最短路径，则这个结论与所有已找到最短路径的点应该包含在集合s 中的 条件相冲突。通过以上的分析，可以得出d i j k s t r a 算法的基本步骤为： 1 定义集合s ，用来存储已经找到最短路径的点，初始时集合s 中为空，所有 要搜索的点的权重置为无穷大一。 2 选择起始点v s ，将v s 的权重c o s t s 为o ； 3 在己设置权重、但没有放入集合s 的节点中寻找权重最小的节点v i ，将v i 插入集合s 中： 4 寻找与v i 相邻但没有放入集合s 的节点v j ，如果c o s t j c o s t i + l ( c 0 s t i 、 c o s t j 分别为节点v i ，v j 的最短路径长度，l 为v i 和v j 之间弧的权重) ，则将- 节点v j 的权重置为c o s t i + l ； 5 重复进行3 、4 步，直到所有节点都进入集合s 或者终点v e 已经进入集合s ， 这时候终点v e 的权重c o s t e 就是源点v s 到终点v e 的最短路径的长度。 o l o ( 2 ) ( 4 )( 5 ) 1 2 ( 3 ) 1 2 图3 - 1 0d i j k s t r a 算法的寻径过程 上图为一个简单的无向加权图，图中边上的值为权值，设要查询从点1 到点 g i s 中最短路径问题的研究与实现 4 的最短路径，在图l 的初始状态下，每一个点的最短路径值都设为无穷大。 第一步( 图2 ) ，从起点1 开始搜索，点l 到本身的最短路径为0 ，因此将点 l 的最短路径长度设为o ，并标记点1 为已找到最短路径的状态，即图中的深灰 色状态，同时搜索与点l 相邻但没有确定找到最短路径的节点2 、3 ，比较点1 的最短路径值+ 边的权值与点2 、3 目前的最短路径值的大小，取小值放入点2 、 3 的最短路径值中，即1 0 和1 2 但是此时1 0 和1 2 并不一定是点2 和点3 真正 的最短路径，因此将点2 和点3 标记为已搜索过但还没有确定最短路径的状态， 即图中的浅灰色状态。 第二步( 图3 ) ，从已搜索但还没有确定最短路径的点中，获取当前最短路径 长度最短的点，即点2 ，把它标记为已经找到最短路径状态，并搜索与其相邻但 没有确定找到最短路径的节点，即图中的点4 ，经过比较将点4 的最短路径值设 为点2 的最短路径值+ 边( 2 。4 ) 的权值，即2 5 。 第三步( 图4 ) ，从图3 中看出点3 和点4 处于已搜索但没有确定找到最短路 径，其中点3 的最短路径值最小，因此将点3 标记为已找到最短路径的状态， 然后考察点4 ，点4 当前最短路径值为2 5 ，而点3 最短路径值+ 边( 3 ，4 ) 的 权值为2 3 ，因此将点4 的最短路径值设为2 3 。 第四步( 图5 ) 。由于仅有点4 处于已搜索但没有确定最短路径的状态，因此 直接将点4 设为已找到最短路径状态，其最短路径值就是当前最短路径值，即 2 3 。 至此，最短路径查找完成。 d i j k s t r a 算法的c 语言描述为： v o i ds h o r t p a t h ( v e r t e xv i i ，i n tn ，i n ts ) f o r ( i n ti n d e x = 0 ；i n d e x ( n ：i n d e x + + ) f v i n d e x w e i g h t = m a x ； v s = o ： f o r ( i n ti n d e x = 0 ；i n d e x ( n - 1 ：i n d e x + + ) d o u b l ew = m a x ： g i s 中晟短路径问题的研究与实现 i n ti ： f o r ( i n ti n d e x l = o ：i n d e x l n ：i n d e x l + + ) i f ( ! ( i s l n ( v i n d e x l ，s ) ) c o s t i n d e x l w ) i = i n d e x l ： v - - c o s t i n d e x l ： ) i n s e r t ( v i i 3 ，s ) ： f o r ( i n d e x l = o ；i n d e x l n ；i n d e x l + + ) i f ( ! ( i s l n ( v i n d e x l ，s ) ) c o s t i + l i ，j c o s t i n d e x l c o s t i n d e x l ：c o s t i + l e i ，j ： )： j i n ti s l n ( v e r t e x ，s ) 判断点v e r t e x 是否在集合s 中 v o i di n s e r t ( v e r t e x ，s ) 将点v e r t e x 插入集合s 中 ) 从上文可以看出，此算法的运行时问在第一个f o r 循环中是n 次，第二个f o r 循环中由于嵌套了一个f o r 循环，因此执行时间为n 2 ，因此d i j k s t r a 算法的时 间复杂度为0 ( n 2 ) 。空间复杂度视采用的存储方式而定，如粲是采用邻接矩阵， 利用二维数组来存储图，则空间复杂度为s ( n 2 ) ，如果采用邻接表或其它链表 形式，则会降低空间复杂度，最少可以达到s ( n ) 。 g i s 中最短路径问题的研究与实现 第四章基于a r c e n g i n e 的d ij k s t r a 算法的实现 4 1 实现目标 本研究要实现的目标是在一个城市级规模的道路网中快速寻找最短路径，并 记录路径和长度等信息。在实际环境中，两个路口之间的最短路径并不一定是 距离最短，丽是距离较短，路况较好的路径，这跟图中的路径权值是相对应的， 所以程序实现中计算最短路径应当以道路权值为标准计算最短路径。程序实现 的两大要求是： ( 1 ) 快速 程序实现主要分为两大步，一是建立邻接多重表，二是计算最短路径，由于 建立邻接多重表只是在程序初始化时执行，一旦邻接多重表建立完成，则在多 次计算最短路径时不再需要重新建立，因此对时间的要求主要在于第二步搜索 最短路径。在本程序使用的数据中，任意两点之间的最短路径搜索效率应该明 显优于传统的d i j k s t r a 实现方法( 路径显示过程的时间消耗暂时不做考虑) 。 ( 2 ) 准确 本研究以d i j k s u a 算法为基础，d i j k s t r a 算法计算所得的最短路径不是较优 解，而是最优解，因此在实际的程序实现中，所得最短路径也是最优解( 默认 道路权值与实际道路的长度和路况相符) 。 4 2 实现环境 4 2 1 数据 本研究使用的数据为a r c g i s 平台的s h a p e f i l e 数据，分为点、线两层，点 层代表城市道路的路1 3 节点，线代表路段，其中每个路1 2 1 节点都与道路的首尾 相连。 1 4 g i s 中最短路径问题的研究与实现 愿始数据 扩展后的数据 图4 一i 道路网数据 原始的道路网数据大约有5 0 0 0 个路口，6 7 0 0 条道路，为了更好地体现本文 中算法实现的效率，本文将原始数据扩大了9 倍，最终参与运算的数据中约有 4 2 0 0 0 多个路口和6 2 0 0 0 多条道路。扩大后的数据虽然并不能直接模拟某一具体 城市或地区的道路网数据，但是由于本文主要研究最短路径算法在具体平台上 的实现，所实现的程序也是一种算法验证程序，并不是实用系统，因此扩大后 的道路网数据完全可以满足计算要求，并且这一数据量也代表了现代大城市的 道路网真实数据量。可以较好的模拟出真实的算法实现效率。计算最短路径应 当以道路权值为标准，本程序中已经将道路的权值与路径长度相乘并存入道路 的w e i g h t 字段中，因此在程序运行中不需要同时取道路长度和权值，只需要取 w e i g h t 字段值进行计算。 4 2 2 软硬件平台 本研究基于a r c g i se n g i n e 平台，实现语言为| i sc # 语言，编程环境为m s v i s u a ls t u d i o n e t 2 0 0 5 。 g i s 中最短路径问题的研究与实现 硬件；c p u ：p i i im 处理器，主频1 0 0 0 m ，二级缓存5 1 2 k 内存：5 1 2 ms d 内存，频率1 3 3 m h z 硬盘：8 0 g5 4 0 0 r p m ，8 m 缓存 操作系统：w i n d o w s x ps p 2p r o f e s s i o n a l g i s 平台：a r c g i se n g i n e9 2 开发环境：m i c r o s f tv i s u a ls t u d i o n e t2 0 0 5w i t hf r a m e w o r k 2 0 4 3a r c g l s 的数据结构 美国环境信息研究所( e s r i ) 的a r c g i s 系列产品是目前应用最为广泛的g i s 平台之一。强大的功能使其在各类大中型应用系统中能很好的适应需求。a r c g i s 系列产品主要支持的数据类型有s h a p e f i l e 、c o v e r a g e 、g e o d a t a b a s e 等，其中 最常用的是s h a p e f i l e 类型。s h a p e f i l e 存储了非拓扑的几何信息，它把所有 的地理要素分为点、线、面三种基本类型，并且在s h a p e f i l e 文件中并不存储 多余信息。因为这种格式不需要处理拓扑数据结构的开销，所以它编辑迅速， 需要更少的磁盘空间，更容易读写。二- 个s h a p e f i l e 包括一个主文件，一个索 引文件和一个d b a s e 表。主文件包括文件头和可变长的记录，每个记录描述了 一个s h a p e 的信息；索引文件记录了相应记录在主文件中相对主文件开始处的 偏移量；d b a s e 文件记录了每个记录的属性，其记录顺序必须与主文件记录的 顺序一致。 4 4 算法实现的优化策略 4 4 1 数据预处理 d i j k s t r a 算法本身是一种贪婪算法，目前还找不到什么捷径可以不用遍历整 个图而找到最短路径，为了尽量减少最短路径消耗的时问，应该使数据规范化， 并尽量在数据中提供查找最短路径所需的信息。最短路径的基础是图的拓扑结 构。而s h a p e f i l e 数据不包含拓扑关系，所以要为s h a p e f i l e 建立拓扑关系将涉及 到大量的几何运算，这个过程将会耗费大量的时间。但是，可以利用s h a p e t i l e 可以附带属性数据这样一个特点，间接为s h a p e f i l e 附带上简单的拓扑关系。道 1 6 g i s 中最短路径问题的研究与实现 路数据包括点和线两类，因此就有两种附带拓扑关系的方法，一是在每个点元 素的属性中附带与其相接的线元素的d ，或直接附带与其相邻的点元素的d ： 二是在每个线元素的属性中附带两端的点元素的d 。相比较而言，第二中方法 更为可行，原因如下： ( 1 ) 点元素和线元素的关系为hn ，也就是说一个点元素可能会找到多个线与 其相连，如果按最大值为点元素增加属性，则肯定会浪费太量窑间，如果按平 均数来增加属性，又会损失大量拓扑信息。 ” ( 2 ) 线元素和点元素的关系始终为1 ：2 ，每个线元素有且仅有一个首点和一个 尾点，只需要为线元素增加首节点d 和尾节点m 两个属性就可以实现，并且 既不丢失拓扑关系，也不会浪费空间。 ( 3 ) 按照第一种方式，则需要使用循环遍历与点相接的线元素，时间开销无法 确定。 ( 4 ) 按照第二种方式，不需要做循环，直接可以取两次属性值进行计算。 图4 - 2 道路数据中附加属性 根据以上分析，最终选择向s h a p e f i l e 的线元素中添加首尾节点的方式来表示 简单的拓扑关系，s t n o d e i d 表示线的起始点i d ，e d n o d e i d 表示线的终止点 i d ( 如上图) 。通过这一处理，在下文建立图的存储结构时。可以很方便的通过 遍历线层元素来建立链表结构。 1 7 g i s 中最短路径问题的研究与实现 4 4 2 存储结构的选择 要做最短路径查询，首先需要建立拓扑结构，拓扑结构在运算的时候是需要 以某种数据结构存储在内存中的。因此，要有效提高最短路径算法，提高建立 拓扑关系的速度是一个重要方面，而要提高建立拓扑关系的速度，则需要设计 一个好的存储结构。 。 无向加权图的存储结构主要有邻接矩阵、邻接表和邻接多重表，其中，邻接 矩阵能够有效的提高节点搜索速度。计算方便，但是，邻接矩阵只适用与数据 量比较少的情况，如果图的顶点( 即路r a 节点) 数达到数千甚至更多的时候， 邻接矩阵的内存开销是无法接受的。前文所述，由于采用二维数组存储，邻接 矩阵的空闻复杂度为s ( n 2 ) ，假设图层中有1 0 0 0 0 个路口节点，保守估计每个 节点之间仅仅用一个d o u b l e 型来表示拓扑关系，则所需要的内存开销为8 1 0 0 0 0 2 7 6 3 m 字节( i m b = 1 0 2 4 x1 0 2 4 字节) 。在具体实现过程中，可能需要 1 g 甚至更多的内存，而且这还不包括程序本身以及操作系统等其它软件占用的 内存，在目前的计算机硬件平台上，这种内存开销是无法得到满足的。因此， 只有在数据量比较小时才会采用邻接矩阵来存储图。 如果采用邻接表来存储图，假设每个路口占用链表中的一个节点，每条道路 占用两个节点，则同样是1 0 0 0 0 个节点的数据，假设平均每个路口与3 条道路 相连，如果按每个节点占用加字节的存储空间，则邻接表的内存开销为4 0 7 x 1 0 0 0 0 t 3 m 字节，可以看出邻接表在空间复杂度方面是远胜于邻接矩阵的。因 此在数据量比较大的情况下，若采用邻接矩阵，则所产生的内存消耗是无法接 受的，只有采用链式存储结构才能满足要求。 由于本研究中在图层属性中加入了一种间接的拓扑结构，即每一个线的属性 中包含了首节点和尾节点的i d 号，所以可以根据线属性中的首尾节点i d 号可 以快速得到首尾节点，因此采用遍历线元素的方式来建立链表。在图论中，无 向图的链式存储方式主要有邻接表和邻接多重表，这两种存储方式在具体应用 中会有什么不同呢? 1 8 g i s 中最短路径问题的研究与实现 - f 图4 - 3 无向加权图g _ 一 如上图所示，图g 为一个无向加权图，若分别采用邻接表和邻接多重表存 储，则存储结构如下： l 2 3 4 5 邻接表 邻接多重表 图4 - 4 无向加权图的两种链式存储 由上图可以看出，图g 中的每个顶点在邻接表和邻接多重表中的存储方式 相同，因此所消耗的存储空间也相同。但是在邻接表中，图g 的每一条边都会 产生两个边节点，分别位于首尾两个节点所在的链表上，而在邻接多重表中， 每一条边只产生一个节点，位于多重链表上，但是，是否因此可以断定邻接表 的内存开销一定大于邻接多重表的内存开销呢? 如下图所示： g i s 中最短路径问题的研究与实现 匡蚤三五j 区三 亘互互 二亟三互工：i i ；互 邻接多重表的边节点 邻接表中的边节点 、图4 - 5 两种链式存储中的边节点 由于邻接多重表中的边节点位于多重链表之上，即相当于每一个边节点同时位 于两个链表上，所以需要通过附加字段( i v e x 和j v e x ) 来指示i l i n k 和v l i n k 应该位于哪一个链表，而邻接表中的边节点则位于单一的链表中。所以邻接表 和邻接多重表孰优孰劣，主要取决于m a r k 字段的长度。如果m a r k 字段占用长 度很小，则可能两个邻接表节点的内存占用会小于邻接多重表，这样邻接表的 内存开销就小于邻接多重表了。在本文中，由于需要通过线节点访问点节点， 因此，邻接表中的m a r k 字段至少需要一个指向点节点的指针v e x ，以及一个 d o u b l e 型的权重字段和i n t 线元素i d 字段，因此每一条线最终的存储要求是2 ( 4 + 8 + 4 + 4 ) = 4 0 字节。而在邻接多重表中，m a r k 字段中只需要一个权重 字段和线元素i d 字段，所以每一条线的最终存储要求是8 + 4 + 4 + 4 + 4 + 4 = 2 8 字节。尽管每一条边在邻接表和邻接多重表中存储时的内存占用只相差1 2 字节， 但是，一旦数据量巨大，或者由于m a r k 字段需要存储的数据较多。则这一差距 将会明显影响程序的内存开销。据此计算，本文中应采用邻接多重表存储无向 加权图。 4 4 3 链表建立的优化 本文通过遍历线层的方式来建立改进的邻接多重表，因此仅仅遍历线层便可 以建立。但是，在实际程序中，不光要取得线元素的信息，同时还要取褥相应 点元素的信息。通过遍历线元素来建立邻接多重表，在获得某一线元素的首尾 节点i d 之后，仍然需要查找与相应i d 号对应的点元素，然后建立线与首尾节 点之间的关联。根据i d 查找点元素，其时间复杂度可以达到0 ( n ) 。所以，整 个建立邻接表过程的时间复杂度可以达到0 ( n 2 ) ，仍然是制约时间效率的一个 因素。如果要有效降低这一过程的时间复杂度，则必须降低查找点元素的时间 开销。要实现这一目标，可以通过建立节点i d 到节点存储位置的索引的方式， 2 0 g i s 中最短路径问题的研究与实现 即预先建立一个数组，数组中存储点节点的指针，而每一个点元素的索引值即 为该点在数组中的存储位置。 整个建立改进的邻接多重表的过程如下( 仍以4 4 2 节中图g 为例) ： ( 1 ) 建立节点数组 i n f o ll i n k i n f 0 2l i n k i n f 0 3l i n k i n f 0 4l i n k i n f 0 5l i n k 图4 _ 6 点节点数组 遍历s h a p e f i l e 中点层元素，获取点的序号和其他可用信息，根据序号将点 的信息存入数组的相应位置中。 通过图的存储结构的介绍可以知道，在处理大量数据的程序中，通常不会采 用数组的形式来存放数据，尤其是二维数组，其内存开销十分巨大。即使是一 维数组，在数据量比较大的时候对内存的要求也是比较高的，因为数组的物理 存储方式决定了数组在使用内存时必须要系统为其分配连续的内存区域，如果 系统中的空闲内存足够，但是却找不到整块的足够大的内存区域，同样无法给 数组分配内存。那么在本文的优化中，采用数组的形式存储点是否会影响整个 程序的空间效率呢? 4 x 1 0 0 0 0 字节 连续空间 4 0 x 1 0 0 0 0 字节 非连续空间 图4 7c # 中的自定义类实例数组的物理存储结构 2 l g i s 中虽短路径问题的研究与实现 由于本程序的实现语言为c # ，而点节点、边节点等均为自定义类，假设点节 点类的大小为4 0 字节，在c # 语言中，定义一个大小为1 0 0 0 0 的点节点类的数组， 程序并不会真的分配一个连续的4 0 1 0 0 0 0 字节的空间，而是仅仅分配一段连 续的4 x1 0 0 0 0 的空间( 如上图) ，数组中的每一个元素也并不是一个真正的点 节点对象，而仅仅是一个指向点节点对象的4 字节的指针( 3 2 位系统中的指针 大小也是3 2 位) ，只有对每一个数组元素重新生成一个真正的对象之后，系统 才会分配出4 0 1 0 0 0 0 字节的空间来存储点节点。但是，此时的4 0 1 0 0 0 0 字 节并不是连续的内存空间，而是散列的。连续的内存空间仍然只是4 1 0 0 0 0 字 节，所以，采用数组的方式来存放节点，并不会给内存开销造成很大压力。 ( 2 ) 建立邻接关系 遍历线层元素，并获得线中的首尾节点i d 属性i 和j ，i d 属性即点的序号， 也就是点在数组中的位置，因此获得i d 属性之后不需要通过遍历线层获得点， 而是直接访问数组中第i 个和第j 个元素获得首尾节点，而后分别给两个节点 建立一个新的邻接关系( 即边节点) 。如下图建立图g 的边1 4 邻接关系： i n f o ll i n k - 一1 4 1 1l 1 4i l i n f 0 2l i n k i n f 0 3l i n k i n f 0 4m l 卜 i n f 0 5l i n k 图4 - 8 邻接多重表的建立 以上的两个步骤时间复杂度都为0 ( n ) ，而且两步是并列的，因此整个建立 邻接多重表的过程的时间复杂度为0 ( n ) 4 4 4 搜索策略的优化 搜索是最短路径查找的主体，也是最短路径算法中时间开销的主要部分，如 何尽量缩短搜索时间是降低最短路径算法复杂度的关键。由前文可以知道， d i j k s t r a 算法主要有两个搜索过程，第一个搜索过程为搜索节点中已经设置过权 重但没有放入集合s 的点中权重最小的节点，以往的算法实现过程往往采用标 记法，对设置过权重的节点设置标记，搜索时仅仅搜索那些已标记的节点，由 于需要判断节点标记，实际上这种方式仍然需要程序遍历所有节点，设置标记 g i s 中最短路径问题的研究与实现 的方式并未有效降低时间复杂度。仍以3 3 节中d i j k s t r a 算法的图解为例： o 1 0 ( 1 ) r ，( 2 ) ( 4 ) ( 5 ) 1 2 ( 3 ) 1 2 圈4 - 9d i j k s 扛a 算法的寻径过程 从第二步开始，为了寻找己搜索过但还没有最终确定最短路径的点，程序通 常需要遍历整个邻接多重表，查找标记的点，这一过程的时间复杂度为0 ( n ) ， 而整个最短路径搜索过程也许需要n 次遍历才能完成，所以整个寻径过程的时 间复杂度可以达到0 ( n 2 ) 。所以要加快搜索效率，只有缩小遍历的范围。以上 图第二步为例： o 垂合d n 图4 - 1 0 移动节点至集合o p e n 将已搜索但还没有确定最短路径的点放进单独的集合o p e n 中( 邻接关系保持不 变) ，则每次只需遍历0 p 饥集合，找出最短路径值最小的点，并移出集合o p e n ， 同时将与该点相邻的点放入集合0 p c | 1 即可，这显然会大大降低搜索的时间开销。 g i s 中最短路径问题的研究与实现 采用以上方法之后，可以看出目前算法中的第二个搜索过程就是从集合 o p e n 中查找最短路径值最小的点。由d i j k s t r a 算法可以看出，如果假设平均每 一个点都和4 个点邻接，则每从集合o p e n 中移出一个点，将会有四个点进入集 合o p e n ，即o p e n 集合的规模会逐渐增加。遍历集合o p e n 的时间复杂度最大可 以达到o ( n 一1 ) 。如果能进一步降低这一过程的时间复杂度，也将有效提高寻 径的效率。本研究采用了升序插入集合的方式，有效降低了时间开销： a ， b 图4 - 1 1 随机序链表和升序链表 上图中，a 是随机排列的链表，b 是升序排列的链表。将一个节点随机插入a 中 时，直接插在首节点位置即可，其时间复杂度为o ( 1 ) ，而要从a 中取得最小值 的节点，则需要遍历整个链表，这一过程的时间复杂度为o ( n ) ，所以整个过程 的时间复杂度为o ( n ) 。相反在b 中，如果要将一个节点升序插入链表中，则时 间复杂度仅为o ( ( n + 1 ) 2 ) ，因为插入过程并不需要遍历整个链表，仅需遍历 到比要插入的节点值大的链表节点就可以。而如果要从链表b 中取得最小值的 节点，则只需要取链表第一个节点即可，时间复杂度为o ( 1 ) ，所以整个过程的 时间复杂度为o ( ( n + 1 ) 2 ) 。可以看出，采用升序插入集合的方式可以有效降 低时间复杂度。 4 4 5 邻接多重表的重复使用 通过以上优化，最短路径的计算在时间效率上已经达到了一个较为满意的水 平，而空间复杂度也处于完全可接受的范围。但是问题也随之而来。由于搜索 策略的优化，在搜索过程中将会随时从已建立的邻接多重表中摘取点节点放入 集合o p e n 中，也会随时从集合o p e n 中移出已找到最短路径的节点。这一方式 在一次最短路径查询中能够有效提高效率，但是在做下一次查询时，由于邻接 多重表被改动，无法完成下一次查询。由上文可以看出，建立邻接多重表时需 要访问地图图层，也就是s h a p e f i l e 文件，需要遍历点层和线层元素，这一过程 g i s 中最短路径问题的研究与实现 的时间开销是非常大的，在数据量较大的情况下，其消耗的时间可能无法接受。 所以如果不解决这一目题，则这一算法优化方案就失去了实用性。 邻接多重表 图4 - 1 2 寻径中的点节点移动 为了解决这一问题，本文在实现过程中增加了一个数据类型s e a r c h l i n k ，这 相当于一个指向邻接多重表中点节点的指针，所有对节点的删除插入操作均由 s e a r c h l i n k 来完成： 集合c l o s e 集合o p e n 邻接多重表 图4 - 1 3s e m - c h l i n k 代替点节点移动 g i s 中最短路径问题的研究与实现 如上图所示，所有需要对邻接多重表中节点进行操作的部分都可以通过建立 一个指向该节点的s e a r c h l i n k 指针来完成，而原始的邻接多重表在搜索过程中 没有做任何改动，所以一旦邻接多重表建立完成，则可以进行多次最短路径查 找。同时，由于s e a r c h l i n k 仅仅是一个指针类，所以在实例化的时候只占用很 少的内存，因此不会增加过多的内存开销。采用这种方式进行最短路径查找， 可以做到“一次建立，多次使用”，只需要在程序装载s h a p e f i l e 之后建立一次邻 接多重表，在下一次装载s h a p e f i l e 之前，无论搜索多少次最短路径，都不再需 要重新建立邻接多重表，并且c 静开发环境的内存回收机制可以保证s e a r c h l i n k 实例不再使用之后及时回收内存，所以这完全可以满足实际使用的要求。 4 5i ) ij k s t r a 算法的实现 4 5 1 程序功能和程序界面 图4 一1 4 程序的功能界面 程序直接采用a r c g i se n g i n e 的控件实现地图的浏览查询等基本操作，主要 包括a x m a o c o n t r o l 、a x t o c c o n t r o l 、a x t o o l b a r c o n t r o l 这三个控件。程序通过 打开按钮载入数据，通过工具一生成拓扑命令建立邻接多重表，利用选择按钮 点选起点和终点，并通过“设为起点”和“设为终点”按钮进行设定，最后按 “最短路径”按钮进行最短路径查找。查找完成后程序将会给出寻径结果已经 寻径时间( 不包含路径显示过程花费的时间) 。由于本文研究的主要内容是最短 路径的优化实现，因此界面设计并不是考虑的重点。 4 5 2 实现过程及其算法分析 为了实现d i j k s t r a 算法，并按照4 4 所述对算法进行优化，在程序中首先 g i s 中最短路径问题的研究与实现 引入三个类： c l a s sv e r t e x 顶点类 p u b l i ci n ti d ； p u b l i ci n ts e a r c h e d ；0 表示从来没有搜索过，表示搜索过，但 没有完成，表示搜索完成，该点的最短路径已经找到 p u b l i cl p o i n tp p o i n t ： p u b l i cv e r t e xp r e y ： p u b l i cv e r t e xn e x t ； p