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

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

的。

4)找到点i的前一点。从已标记的点中找到

直接连接到点i的点j3,作为前一点,设置:

i=j

3

所在边的权值进行顺序排列,这样每循环一次即

可取到符合条件的点,可大大提高算法的执行效率。另外,GIS中的数据(如道路、管网、线路等)要进行最短路径的计算,就必须首先将其按结点和边的关系抽象为图的结构,这在GIS中称为构建网络的拓扑关系(由于这里的计算与面无关,所以拓扑关系中只记录了线与结点的关系而无线与面的关系,是不完备的拓扑关系)。如果用一个矩阵来表示这个网络,不但所需空间巨大,而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。

网络在数学和计算机领域中被抽象为图,所以其基础是图的存储表示。一般而言,无向图可以用邻接矩阵和邻接多重表来表示,而有向图则可以用邻接表和十字链表[4]表示,其优缺点的比较见表1。

　　5)标记点i。如果所有点已标记,则算法完全推出,否则,记k=i,转到2)再继续。

2　已有的Dijkstra算法的实现

从上面可以看出,在按标记法实现Dijkstra算法的过程中,核心步骤就是从未标记的点中选择一个权值最小的弧段,即上面所述算法的2)～5)步。这是一个循环比较的过程,如果不采用任何技巧,未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍,在大数据量的情况下,这无疑是一个制约计算速度的瓶颈。要解决这个问题,最有效的做法就是将这些要扫描的点按其

表1　几种图的存储结构的比较

Tab.1　TheComparsionofSeveralGraphforStoringStructures

名　称邻接矩阵邻接表十字链表邻接多重表

实现方法二维数组链表链表链表

优　　点　　　　

1.易判断两点间的关系2.容易求得顶点的度1.节省空间2.易得到顶点的出度1.空间要求较小

2.易求得顶点的出度和入度1.节省空间

2.易判断两点间的关系

1.不易判断两点间的关系2.不易得到顶点的入度

O(n+m)或O(n3m)

缺　　点　　　　　　　占用空间大

时间复杂度　　　　　　　　

O(n2+m3n)

结构较复杂结构较复杂

同邻接表同邻接表

　　目前,对于算法中快速搜索技术的实现,主要有桶结构法、队列法以及堆栈实现法。TQQ、DKA以及DKD在这方面是比较典型的代表。TQQ虽然是基于图增长理论的,但是快速搜索技术同样是其算法实现的关键,它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程[1]。

DKA和DKD是采用如图1所示的桶结构来支持这个运算,其算法的命名也来源于此。在DKA算法中,第i个桶内装有权值落在[b3i,(i+1)3b)范围内的可供扫描的点,其中b是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护,这样每个点有可能被多次扫描,但最多次数不会超过b次。最坏情况下,DKA的时间复杂度将会是O(m3b+n(b+C b)),其中,C为图中边的最大权值。DKD将点按权值的范围大小分装在两个级别的桶内,高级别的桶保存权值较大的点,相应的权值较小的点都放在低级别的桶内,每次扫描都只针对低级别桶中的点。当然随着点的插入和删除,两个桶内的点是需要

动态调整的。在DKA算法中,给每个桶一定的范围以及DKD中使用双桶,在一定程度上都是以空间换时间的做法,需要改进

。

图1　一个桶结构的示例

Fig.1　AnExampleoftheBucketDataStructure