基于Dijkstra算法改进的海量数据最优路径计算方法研究与实现

王兆南

(浙江大学理学院，浙江杭州3100127)

基于Dijkstra算法改进的海量数据最优路径计算方法研究与实现

王兆南

(浙江大学理学院，浙江杭州3100127)

针对传统Dijkstra算法在应用中存在的不足，提出一种面向海量数据的基于传统Dijkstra算法的最优路径搜索方法，以避免大量无用节点参与计算，严重制约计算效率。通过对路网关系制表来表达节点与路段的关系，解决使用相邻矩阵计算量大的问题。此外，利用监测得到的实时速度进行加权，实现最短时间路径的计算。

Dijkstra算法;海量数据;最优路径

一、引 言

面对城市的日益发展和人们生活水平的提高，城市汽车不断增加，过多的车辆给道路交通带来了过重的负荷。车道的频繁整修，节假日的交通管制，都会给道路带来一定的改变，但是交通部门并不能及时地公布一些车道施工的信息，或者居民不能及时得到已经发布下来的信息，都给居民生活带来了一些麻烦。通过道路监测与发布系统的建立来及时获取和发布道路信息将方便人们的出行。本文中的最优路径分为距离最短路径和时间最短路径两种，其中后者算法是在前者算法基础上拓展得到的。目前，最短路径的算法有很多，本系统从最基本的最短路径的计算方法——Dijkstra算法出发，寻找出一种适合海量数据运算的方法。

二、经典Dijkstra算法的主要思想［1］

Dijkstra算法的基本思路是：假设每个点都有一对标号(dj，pj)。其中，dj是从起源点s到点j的最短路径的长度;pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：

1)初始化。起源点设置为：① ds=0，ps为空;②所有其他点：di=∞，pi为空;③标记起源点s，记k=s，其他所有点设为未标记的。

2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置

式中，lkj是从点k到j的直接连接距离。

3)选取下一个点。从所有未标记的结点集M中，选取dj中最小的一个i：di=min(dj，M)。点i就被选为最短路径中的一点，并设为已标记的。

4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，设置：i=j*。

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

三、本系统最短路径的实现

可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的步骤2)～步骤5)。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中，那么要选择一个权值最小的距离就必须把所有的点都扫描一遍，在大数据量的情况下，这将严重制约计算速度。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边进行顺序排列，这样每循环一次只能取到符合条件的点，排除了大量不相连的点，可大大提高算法的执行效率。此外，线路要进行最短路径的计算，就必须构建网络的拓扑关系。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。

本文采用的算法在原有的Dijkstra进行了优化［2］。利用Access数据库A表达路网的拓扑关系，记录了节点与路段间的关系和路段的长度，由于是单向路网，为了便于计算，分别以起始节点SNode和终点节点Enode进行排序，并得到两组数据，一起组成“起终点连接数据.dbm”文件。利用Access数据库B记录1～555节点的相邻连接点的个数和累计的节点个数，累计节点数主要是为了方便算法的实现。本系统的实现过程如下。

首先需要进行数据库连接，将数据库中的数据赋到相应的变量中。AA1、BB1、CC1、DD1是以起始节点SNode排序生成的一维数组，其中，AA1对应起始节点SNode;BB1对应终点节点Enode;CC1对应路段长度;DD1对应路段编号。AA2、BB2、CC2、DD2是以ENode排序生成的一维数组，其中，AA2对应ENode;BB2对应SNode;CC2对应路段长度; DD2对应路段编号。IndexA1()和IndexA2()为二维数组，其中，IndexA1()的第1项对应累计数1，第2项对应某一起点与其相邻的终点的个数;IndexA2()的第1项对应累计数2，第2项对应某一终点与其相连的起点的个数。变量与数据库字段的相关关系见表1和表2。

表1 数据库A中获取的变量

表2 数据库B中获取的变量

1.空间最短路径

空间最短路径的算法的流程图如图1所示。

搜索与ll相连接的点，是先以ll为起点，寻找与ll相连的终点，而以ll为起点得到的终点搜到之后，再以ll为终点，寻找与ll相连的起点的点，算法过程与上面一样。经过两个循环便将与ll相连的点全部找出，再从中找出长度最短的点，赋给Min-Point。如此循环完成空间上最短路径的搜索。

2.时间最短路径

时间最短路径的算法和空间最短路径算法的流程基本相同，其算法流程图如图2所示。

图1 空间最短路径算法流程图

图2 时间最短路径算法流程

主要代码思想如下：首先进行初始化，初始化过程与空间最短路径的过程一样，开始搜索与ll相连接的点，先以ll为起点，寻找与ll相连的终点，主要代码和空间最短路径的过程类似。在过程中要对路况监督时得到的速度进行匹配，以解决两个模块使用的表顺序不一致的问题。速度求得之后，便可进行时间的计算。求出的是走到此点所花的累积时间S1，再以ll为起点搜到终点之后，再以ll为终点，寻找与ll相连的起点的点，算法过程与上面一样。经过两个循环便将与ll相连的点全部找出，再从中指出时间最短的点，赋给MinPoint。

如此循环完成时间上的最短路径的搜索。

四、最短路径功能实现

最短路径的搜索及结果在地图上显示的全过程如图3所示。

图3 路径选择实现过程流程图

主要实现的功能有：在组合框中利用模糊匹配进行选择路口的选择;在列表框中显示选择的要经过的路口的信息;对列表框中的信息进行删除、上移、下移基本操作;实现空间时间最短路径的计算;在地图上实现最短路径的高亮显示。

1.最短路径计算

对于空间最短路径的计算，依照ListView中所选择的点的顺序多次调用ShortPath()过程实现，时间最短路径的计算调用TShortPath()过程实现。

2.结果的地图显示

最短路径计算结束后，经过的路段的编号以字符串的形式储存在SumPath的变量中，利用Split将SumPath中的路段号提取出来放入一个数组。给搜索的路段进行着色，将最短路径进行高亮显示，渲染后的效果如图4所示。若是空间最短，在最短路径的窗口的查询结果中展现整段路程的最短长度;若是时间最短，记录下所花的最短的时间。

图4 地图高亮显示的效果

如要从四平路国泰路出发经过控江路军工路，最后抵达军工路殷行路，需要知道空间上的最短路径。打开主界面的路径选择菜单，在选择最短路径类型栏中选择空间最短，按照顺序将3个路口的名称输入，单击计算，便出现如图4所示的结果。系统会在最短路径页面的最下方查询结果的文本框中显示“从起点四平路国泰路到终点军工路殷行路空间的最短路程为8 797.934 m”。同时，在主界面的地图上还会用橙色标出最短路径经过的路线。

五、结束语

本文通过对路网关系制表来表达节点与路段的关系，解决了使用相邻矩阵计算量大的问题。此外，利用监测得到的实时速度进行了加权，实现了最短时间路径的计算，并对最短路径进行高亮显示，使路线一目了然。但是，本方法实现的过程还有可以改进的地方，如最短路径的模型相对简单，可以加入车道信息和转向信息等。

［1］ 乐阳，龚健雅.Dijkstra最短路径算法的一种高效率实现［J］.武汉测绘科技大学学报，1999，24(3)：209-211.

［2］ 孙庆珍，李宏伟.GIS中最短路径算法的研究以及在VB中的代码［J］.电脑编程与维护，2005(8)：30-32.

Mass Data Optimal Path Searching Using an Improved Dijkstra Algorithm

WANG Zhaonan

0494-0911(2012)09-0032-03

P208

B

2012-07-16

王兆南(1990—)，男，山东肥城人，主要研究方向为地理信息系统应用与开发。