Dijkstra最短路径算法的一种高效率实现(3)

Dijkstra最短路径算法的一种高效率实现

3　本文提出的Dijkstra算法实现

3.1　网络拓扑关系的建立

上面介绍的各种图的存储结构考虑了图在理论上的各种特征,如有向、无向、带权、出度、入度等。而GIS中的网络一般为各种道路、管网、管线等,这些网络在具有图理论中的基本特征的同时,更具有自己在实际中的一些特点。首先,在GIS中大多数网络都是有向带权图,如道路有单双向问题,电流、水流都有方向(如果是无向图也可归为有向图的特例),且不同的方向可能有不同的权值。更重要的一点是,根据最短路径算法的特性可以知道,顶点的出度是个重要指标,但是其入度在算法里则不必考虑。综合以上4种存储结构的优缺点,笔者采用了两个数组来存储网络图,一个用来存储和弧段相关的数据(Net-ArcList),另一个则存储和顶点相关的数据(Net-NodeIndex)。Net-ArcList用一个数组维护并且以以弧段起点的点号来顺序排列,同一起点的弧段可以任意排序。这个数组类似于邻接矩阵的压缩存储方式,其内容则具有邻接多重表的特点,即一条边以两顶点表示。Net-NodeIndex则相当于一个记录了顶点出度的索引表,通过它可以很容易地得到此顶点的出度以及与它相连的第一条弧段在弧段数组中的位置。此外,属性数据作为GIS不可少的一部分也是必须记录的。这样,计算最佳路径所需的网络信息已经完备了。在顶点已编号的情况下,建立Net-ArcList和Net-NodeIndex两个表以及对Net-ArcList的排序,其时间复杂度共为O(2n+lgn),否则为O(m+2n+lgn)。这个结构所需的空间也是必要条件下最小的,记录了m个顶点以及n条边的相关信息,与邻接多重表是相同的。图2是采用这个结构的示意图。3.2　快速搜索技术的实现

无论何种算法,一个基本思想都是将点按权值的大小顺序排列,以节省操作时间。前面已经提到过,这两个算法都是以时间换空间的算法,所以在这里有必要讨论存储空间问题(这部分空间的大小依赖于点的个数及其出度)。根据图中顶点和边的个数可以求出顶点的平均出度e=m n(m为边数,n为顶点数),这个数值代表了图的连通程度,一般在GIS的网络图中,e∈[2,5]。这样,如果当前永久标记的点为t个,那么,下一步需扫描点的个数就约为t～4t个。如果采用链表结构,按实际应用中的网络规模大小,所需的总存储空间一

般不会超过100K。所以完全没有必要采用以时间换空间的做法,相反以空间换时间的做法是完全可行的。在实现这部分时,笔者采用了一个FI2

排序和删除,FO队列,相应的操作主要是插入、

插入和删除的时间复杂度都是O(1),所以关键问题在于选择一个合适的排序算法。一般可供选择的排序算法有快速排序、堆排序以及归并排序等,其实现的平均时间都为O(nlgn)。经过比较实验,笔者选择了快速排序法。另外,VisualC++提供的run2time库也提供了现成的快速排序的函数qsort(　)可供使用

。

图2　基于最佳路径计算的网络拓扑表示

Fig.2　ThePresentationoftheNetworkTopology

UsedforComputingtheShortestPath

按照以上思路,笔者用VisualC++实现了吉

以北京的街奥之星(GeoStar)中的最佳路径模块。

道为数据(共6313个结点,9214条弧段(双向)),在主频为133、硬盘为1G、内存为32M的机器上,计算一条贯穿全城、长为155.06km的线路,约需1s～2s。如图3所示。