基于GIS的Dijstra最短路径算法研究

冯莹莹

(阜阳师范学院信息工程学院,安徽 阜阳 236041)

基于GIS的Dijstra最短路径算法研究

冯莹莹

(阜阳师范学院信息工程学院,安徽 阜阳 236041)

最短路径是GIS在应用中的主要问题之一，目前提出的求取最短路径的算法很多，其中Dijkstra算法是使用最为普遍。通过对传统的Dijkstra算法在GIS应用中的分析和研究,对算法的数据结构和存储方式进行了优化。复杂性分析比较以及仿真分析证明该改进算法的效率优于传统Dijkstra算法，既节省了存储空间，又提高了程序执行效率。

GIS；数据结构；Dijkstra算法；存储方式

1 传统Dijkstra算法

Dijkstra 算法是以路径长度递增的次序来产生最短路径的算法，主要通过一个源节点不断增长找到最短路径。下面根据最短路径算法即邻接矩阵结构形式的Dijkstra算法来介绍其实现过程。

设一幅具有N个节点的带权有向图G,用邻接矩阵Cost来表示，其中弧〈Vi,Vj〉的权值以Cost[i,j]来表示，当Vi到Vj走不通时,则总邻接矩阵表示为Cost[i,j]=∞。设S为起始点，同时设置一个辅助向量DI，每个DI[i]表示从起始点S到每个终点Vi的最小权值。根据设置的邻接矩阵特点，设所有结点的集合称为U，并令P为已经找到的从起点出发的最短路径的终点集合,那么其向量的初始值为：DI[i]=Cost[P,i]，Vi∈U。其中P={VP},根据最短路径算法公式计算分析，从VP出发到图G上其他所有结点Vi可能达到的最短路径长度为设定的初始值公式值。

步1 令P=P∪{Vj}，要想计算得到从VP出发的最短路径的终点节点，选择Vj,使得DI[j]=min{DI[i]|Vi∈U-P}，这个Vj就是获得的最终节点。

步2U-P作为集合，其中包含了很多顶点，为了获取路径长度，可以修改从VP到顶点VK的最短路径长度。当DI[k]> Cost[j,k]+DI[j],转步3。

步3 当出现DI[k]> Cost[j,k] + DI[j]时，就将DI[k]=DI[j]+Cost[j,k]直接赋值操作并重复操作步2和步3共N-1次,该路径是各权值递增的序列。

上面的三步法求得最短路径算法采用的是的邻接矩阵Cost来存储网络图，存储的空间范围是N×N,当图形相对大时，存储的大部分矩阵都是没有意义的[1]。在遍历过程中，Dijkstra算法主要还是按标记法来实现最短路径的搜索，即从未标记的点中找到权值最小的节点，但会出现一种现象，当这些未标记节点以无序的形式存储在一个链表或数组中，如果想获取最小权值节点就必须将这链表或者数组中的所有未标记的节点进行扫描，如果是这样，当一个图集中有大量数据的情况下，就会给最短路径算法的计算速度带来限制。当一个系统被N多用户并发访问时就会出现服务器瘫痪，正是考虑到这种多发访问出现的问题，最短路径采用了同样的原理，算法实现原理中的关键技术为松弛技术，通过反复减小每个顶点实际路径权限的范围值，通过迭代找到最短路径值。

2 Dijkstra算法优化

在GIS系统中要求解2点之间的最优路径，即最短路径算法的实现，具有速度快、占用资源少、稳定性强等优点的Dijkstra 算法是解决该类问题的有效算法，但在特定的环境和大量数据情况下，Dijkstra算法也出现了瓶颈：其遍历的未标记节点过多，重复迭代，导致速度相对下降。为此，笔者对Dijkstra算法进行了深入的分析和研究，采用一种堆排序和邻接表的面向对象的Dijkstra算法的改进算法，具体的算法是基于传统Dijkstra算法本体，对其数据结构和存储方式进行了优化，从而优化了Dijkstra 算法。

2.1 存储方式改进

在GIS中存在着很多重要的空间数据，如线路、标志物、道路灯等，这些都要进行最短路径的计算，而Dijkstra算法是图论计算最短路径的有效算法，因此，GIS中的所有空间数据都要将其转化为结点和边的关系，从而形成图的结构和网络拓朴图的效果。在网络图中的线和点是算法的单位元，Dijkstra算法主要通过这些结点进行计算，GIS中的点、线、面等空间几何数据与面没有计算关系，但GIS中的地理位置信息具有方向性，这些结点、边、方向以及结点的链接点都是计算最短路径的重要信息，在计算过程中都赋有权值[2]。下面主要从3个方面进行优化改进。

表1 算法节点声明

(1)根据GIS图中的形成的网络拓扑结构图的相关重要参数进行设置和计算。算法的存储方式以面向对象为标准进行设定，设S为带权有向图，L为边，V为结点，其中图中的结点数为n，边数为m，将图中的任一结点设为j，而这个j结点的直接前趋结点设为k，P为起始点，U为终点。算法优化的存储方式是面向对象的，因此采用Java语言进行名词声明和定义，其中对结点和相关弧信息进行封装，具体如表1所示。

2)在算法实现过程中存在很多对象类，其中的Lxctor类就封装了集合U-P的结点列表，并且按照结点顺序进行存放。Dijkstra算法中包含一组对象的对象类，其中Lxctor被定义为收集类对象，允许动态的创建数组，也允许对链表中的结点进行增加和删除操作，在Java技术平台下支持的收集类包括LinkedList、Vector、Hashtable等。

3)在Java技术平台下，算法中的最短路径列表即从起点到终点的最短路径，设为对象类critHash，critHash和Lxctor一样也是一个收集类对象，也是Hashtable数组中的一个对象类。当然在Java语言中这2大类也是有所区别的，图信息中的每一个对象元素都对应一个关键字，即关键字与对象元素是一一对应的关系，而算法中的对象类critHash具有这样的特征[3]。通过该对象类将每一个结点到其他结点的最短路径进行封装，并赋予一个关键字，每当搜索过程中发现已经做过标记关键字则该条路径搜索结束，通过这样的对象类封装，可得到结点的最短路径列表，减少搜索范围。

图1 数据结构的时间复杂度优化流程

在存储方式优化过程中还用到了3大辅助对象类：cVeetor、cHash和sHash，对象类cVeetor封装与源点相邻但还未被访问过的结点列表，对象类sHash用于封装出度大于零的结点，对象类cHash则是与sHash中每个结点元素对应的相邻结点列表。通过采用这些对象类对图中的信息进行关联和权值计算，最后优化了最短路径算法。

2.2 数据结构优化

在算法数据结构中，对点和弧都进行了编号和定义，1个弧段是由若干位进行表示，包括弧段编号及权值、弧段起始节点编号、弧段结束节点编号， GIS图中的所有点在数据结构中被标识为一些节点，并形成对应数据信息。正是因为这些点是连接弧段的起始和结束点，在数据结构的所有图信息中，根据点和边的关联，算法中可实现各种矩阵，方便实现各种搜索和运算。因此采用优质稳定的数据结构可大大缩短Dijkstra算法的计算时间，利用先进数据结构体系完成算法从时间复杂度由二阶降到对数阶的完美过渡[4]。具体实现如图1所示。

3 复杂性分析比较与仿真

3.1 复杂性分析及比较

1)时间复杂度分析 笔者采用的是堆栈式的邻接表方式对存储方式和数据结构进行优化。首先将图中的信息节点和弧进行声明定义，并构建弧点矩阵结构，通过动态的收集类进行动态的遍历数组，对最短路径权值进行存储，每一次的遍历都会得到一个节点列表，并对这些节点信息值进行排序，完成优先遍历表，这样大大提高了搜索的时间，通过采用基数堆与Fibonacci堆的组合,其时间复杂度为O(m+nlogn)，在一定程度上提高了运算速度。与传统的Dijkstra算法相比较，具有很大的时间效率优势。

表2 搜索节点数量对比

2)空间复杂度分析 笔者通过改变存储方式，将一个GIS图分为节点和弧段，实现节点弧关联结构体，改变了节点的存储量，减少了遍历的节点数，存储量为O(L+2N)(L为节点列表中同节点关联的所有弧段数目)。同时设两个数组来存储求得的起点到其他所有节点的最短路径值以及排序节点，缓冲搜索时间。而传统Dijkstra算法的空间复杂度为O(N)，相比较而言，提供了存储效率，节省了空间[5]。

3.2 数据仿真实现

针对GIS图的最短路径算法的数据仿真，采用了硬件设备为主频700MHz,内存为1G，安装系统为WindowsXP,并通过.NET Frameworks 3.5[6]实现了算法。搜索节点数量对比结果如表2所示。由表2可知，对Dijkstra算法的存储方式和数据结构的优化可以提高算法的效率和稳定性。

4 结 语

提出了一种基于堆排序和邻接表的面向对象的Dijkstra算法的改进算法，结合传统Dijkstra算法的现状，分析了其在求解最短路径上的瓶颈，对算法实现过程中数据存储方式和数据结构进行了优化[7]，通过对改进后的算法和之前算法空间和时间复杂度上的分析和比较以及仿真试验证明，优化后的算法具有一定的高效性和稳定性。

[1]王战红,孙明明,姚瑶.Dijkstra 算法程序的优化与实现[J].湖北第二师范学院学报，2008 (8)：103-105.

[2]李臣波.一种基于Dijkstra的最短路径算法[J]. 哈尔滨理工大学学报,2008(13)：78-80.

[3]杜兴勇,刘延平,王忠文.Dijkstra算法程序的优化与实现[J].通化师范学院学报,2008(12)：129-131.

[4]陈述彭,鲁爱军,周成虎.地理信息系统导论[M]. 北京:科学出版社,2000.

[5]卢开澄,卢华明.图论及其应用[M]. 第2版.北京:清华大学出版社,1997.

[6]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.

[7]陆锋.最短路径算法:分类体系与研究进展[J]. 测绘学报,2001(15)：116-118.

[编辑] 洪云飞

10.3969/j.issn.1673-1409(N).2012.10.034

TP311.12;O241

A

1673-1409(2012)10-N110-03