基于城市路网的最短路径算法研究

戴建光

(常州市武进规划与测绘院，江苏 常州 213159)

基于城市路网的最短路径算法研究

戴建光*

(常州市武进规划与测绘院，江苏 常州 213159)

最短路径分析是城市路网分析的重要内容之一，本文分析了几种流行的最短路径算法，通过对比其优缺点，得出A*算法比较适合城市路网最短路径分析的结论。基于常州市武进城区路网数据对A*算法进行测试，试验结果表明，在时间效率和准确性方面，A*算法都符合城市路网最短路径分析的要求。

城市路网；最短路径算法；A*算法

1 引 言

城市化的发展和城市道路的不断建设，给人们的生活带来了很大便利，同时城市路网也变得越来越庞大与复杂，对城市路网的分析与利用成为人们密切关注的问题之一。GIS因其强大的网络分析功能在城市路网研究中发挥了重要作用，而路网分析中最基本、最关键的问题是最短路径问题，最短路径分析就是如何在最短的时间内花费最少的代价到达目的地。由于最短路径分析在实际中常用于导航、火警、医疗等应急系统，这类系统对最短路径算法的时间要求比较高(一般要求在 1 s～3 s)，同时在行驶过程中还要求实时计算行驶路线，这就决定了最短路径算法必须是高效率的。

2 主流算法比较

目前国内外针对最短路径的算法主要有单源点最短路径算法Dijkstra算法、全源最短路径算法Floyd算法、启发式搜索算法A*算法等。下面重点研究讨论 Dijkstra算法、Floyd算法、A*算法的原理和三者的对比分析。

2.1 Dijkstra算法

Dijkstra算法是1959年由荷兰计算机学家Dijkstra提出的，它是从一个节点到其余各节点之间的最短路径算法，主要特点是以起始点为中心向外层层扩展，直到到达目标点为止。假设起始节点为s，目标节点为t，路网中每个节点的标号为(di，pi)，di是从起始点s到点i的最短路径长度，pi是从s到i最短路径中i点的前一点，w(k，j)表示点i到点j的距离。算法基本步骤如下：

Step 1：所有节点初始化。起始点ds=0，ps=null，标记起始点，k=s，其他点di=∞，pi=null，均设置为未标记。

Step 2：计算所有已标记的点k到未标记的点j的距离，设置dj=min[dj，dk+w(k，j)]。

Step 3：从未标记的点中选取距离最小的点i，从标记的点中查找与i点直接相连的节点，记pi。设置点i为已标记，并记录为最短路径中的一点。

Step 4：继续分析，直至所有点都被标记，算法结束。

从上述步骤中可以看出，Dijkstra算法的时间复杂度为O(n2)(n为路网中的节点个数)，而且如果想得到任意两个节点之间的最短路径，则需要每次以一个节点为起始点，重复运算n次，则相应的时间复杂度就变成了O(n3)。因为Dijkstra算法计算的是起始点到其他所有节点的最短路径，因此它的时间复杂度比较高，相应的效率较低。

2.2 Floyd算法

Floyd算法是由Floyd提出的，它是通过一个图的权值矩阵求出每两点间的最短路径矩阵。算法思路是从任意一条单边路径开始，两点间相连时以边长定权，不相连权设为无穷大。然后对于每一对节点u和v，判断是否有节点w使得u-w-v的距离比u-v的距离短，如果有，则更新矩阵。算法基本步骤如下：

Step 2：设k=0，权阵D(0)=D。

Step 3：设k=k+1，计算：

D(k)=(dij(k))m×n，k=1，2，…，n

其中：dij(k)=min[dij(k-1)，dik(k-1)+dkj(k-1)]。

Step 4：重复运算，直至k=n完成最短路径分析。

如果需要保留路径信息，要在运算中保留下标信息，即dik+dkj=dikj，或者在运算时将路径信息保存在path矩阵中。

从上述步骤中可以看出，Floyd算法的时间复杂度为O(n3)(n为路网中的节点个数)，时间复杂度依然较高，对于城市路网的最短路径分析效率较低。

2.3 A*算法

A*算法是由Hart、Nilsson、Raphael等首先提出的一种启发式搜索算法，该算法在搜索过程中加入启发因子来缩小搜索范围，从而加快搜索速度。该算法的公式表示为f(n)=g(n)+h(n)，其中，f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。算法基本步骤如下：

Step 1：创建两个表，其中open表存放所有已生成但是还未分析的点，close表存放已经分析的点。

Step 2：计算起始点s的估价值，并放入open表，按照估价值f将open表中的节点排序(最小的在最前面)，从open表中取出估价值f最小的节点n(第一次取得点为起始点)。

Step 3：对取出节点n的所有子节点k进行分析：如果k在open表中，判断k的估价值是否小于open表的估价值，如果是，把n设置为X的父节点，更新open表中的估价值；如果k在close表中，继续分析下一个子节点；如果既不在open表也不在close表中，把n设置为k的父节点，求出k的估价值f(k)，并将k插入open表中。

Step 4：将n节点插入close表中，对open表中的节点重新排序。

Step 5：重复步骤2～4，直至取出的节点为目标节点，最短路径分析完成。

从上述步骤中可以看出，A*算法得出的路径可能不是最短的路径，但是该算法除了考虑起始点到该节点的距离，还对节点到终点的距离进行了估价，这样避免了盲目的搜索，大大缩小了搜索范围，提高了算法的效率，因此针对城市路网，尤其是移动端的城市路网最短路径分析，A*算法有着明显的优势。

3 实验验证

为了验证A*算法是否能在城市路网的最短路径分析中起到实际作用，文章选择了江苏省常州市武进区的一块路网数据(约850个路节点)，如图1所示。

图1 实验区域路网概况图

用java语言在三星平板电脑上开发了Dijkstra算法、Floyd算法和A*算法，分别计算实验路网的最短路径，得到的时间效率对比结果如表1所示。

Dijkstra算法、Floyd算法、A*算法时间效率对比 表1

为了验证A*算法最短路径计算结果的准确性，程序还接入了百度地图的路径查询功能接口以供对比分析，对比结果如图2、图3所示。

通过和百度地图的路径查询功能接口的对比，可以看出，基于A*算法的最短路径分析结果和百度地图分析结果基本一致，而在运行时间上也相差不多，可以满足城市路网的最短路径分析需求。

图2 百度地图路径计算结果(用时198 ms)

图3 A*算法计算结果(用时235 ms)

4 总 结

文章通过Dijkstra算法、Floyd算法、A*算法的对比分析，体现了A*算法的时间效率优势并通过实例证明，同时通过与百度地图路径分析功能的对比，验证了A*算法最短路径分析结果的准确性。通过实际的城市路网数据测试，A*算法在城市路网数据最短路径分析中，效率和准确性方面都取得了比较满意的成果。

[1] 王开义，赵春江，胥桂仙，宋晓宇. GIS领域最短路径搜索问题的一种高效实现[J]. 中国图像图形学报，2003，8(8)：951～956.

[2] 吴必君，李利新，雷小平. 基于城市道路数据库的最短路径搜索[J]. 西南交通大学学报，2003，38(1)：80～83.

[3] 王肖，徐友春，章永进等. 一种基于GIS最短路径搜索的A*改进算法[J]. 计算机系统应用，2008，5：28～31.

[4] 陈波，杨阳，郑文军. 一种基于道路网分层的最短路径算法[J]. 海洋测绘，2006，26(3)：21～23.

[5] 唐一行. 论Floyd最短路径算法在火灾消防救援中的应用[J]. 现代商贸工业，2010，24：383～384.

[6] 朱凯. 应用于公交网络交通中最短路径算法的研究[J]. 信息技术，2012，11(5)：186～188.

[7] 王荣，江东，韩惠. 基于Floyd方法的最短路径算法优化算法[J]. 甘肃科学学报，2012，24(4)：110～114.

Shortest Path Algorithm Based on City Road Network Study

Dai Jianguang

(Changzhou Wujin Planning and Surveying Institute，Changzhou 213159，China)

shortest path analysis is an important part of city road network analysis，this paper analyzed several popular Shortest path algorithm，we got a conclusion that A* algorithm is more suitable for city road network analysis by comparing their strength and weaknesses. Finally the A* algorithm is tested based on Wujin road network data，the test result showed that A* algorithm can meet the requirement of city road network analysis.

city road network；shortest path algorithm；A* algorithm

1672-8262(2016)06-47-03

P208.2，TP391

A

2016—11—08

戴建光(1973—)，男，硕士，高级工程师，从事城市规划与3S技术应用工作。

2016年度江苏省测绘地理信息科研项目(JSCHKY201615)