最短路径算法加速技术及其搜索空间分析

最短路径问题是 GIS 网络分析研究和应用中的重要问题，其在在线地图和导航中应用广泛。最短路径问题的分类多样 [1-5]，本文主要介绍针对道路网络中给定 2 个顶点之间的最短路径计算问题的相关算法。

1 最短路径算法加速技术

近年来，随着道路网络数据规模的增大，一些成熟的加速技术能高效处理大规模数据的最短路径算法。基于 Delling 等的按照算法时间阶段的分类方法 [6]，本文添加了国内外最新最短路径算法研究成果，将其分为 4 个阶段 ：第一阶段是算法理论研究阶段(1959年 ~1999 年)，代表算法有 Dijkstra 算法 [2]、双向搜索算法 [7]、A * 算法 [8] 等 ;第二阶段为经典最短路径加速算法阶段(1999 年 ~2005 年)，代表算法有 Lanmark 算法(地标导向算法 [9])、Reach 算法 [10]、ALT 算法 [11] 等;第三阶段是工程算法研究阶段(2005 年 ~2008 年)，代表算法包含 Arc-Flag 算法 [12]、HH 算法 [13] 和 REAL 算法 [14] 等 ;第四阶段是道路网络加速算法阶段(2008 年至今)，代表算法有 CH 算法 [15]、SHARC 算法 [16] 及其他算法 [17,18] 等。

在实际应用中，由于减少搜索空间策略比设计高效的优先队列策略提高最短路径查询效率的影响要大 [19]，因此众多加速技术策略为减少搜索空间。最短路径算法的研究有众多成果 [20]，但对于最短路径的算法加速技术与搜索空间的研究还有待进一步分析。为了研究各个阶段算法的加速比与搜索空间的关系，本文选取每个阶段的典型方法研究最短路径算法加速技术和搜索空间的定量关系。

Dijkstra 算法是处理最短路径的经典算法，在实际应用中结合堆或者最小优先队列来加速查找效率。Dijkstra 算法计算过程是以起点 s 为根向外搜索构成最短路径生成树，所有搜索空间包含的结点有 3 种状态 ：未通达、已通达以及确认。如果某一结点已经被确认，表示存在 1 条从 s 到达当前结点的最短路径，当终点 t被确认时搜索过程结束。

双向搜索算法是最短路径查询中常用的重要搜索方法，其原理是从起点和终点同时使用单源最短路径算法，将起点和终点搜索到的结点放到同一个最小优先队列中进行排序，当某一个结点与起点和终点之间的最短路径都被计算出来之后，这 2 条最短路径的组合就是起点到终点之间的最短路径。

A* 算法是一种启发式搜索算法，在对搜索到的结点进行堆排序时，使用的不是结点与起点之间最短路径的长度，而是估算的从起点到终点并且经过该点的最短路径长度。在权值为非负的道路网络中，A* 算法在确保最终搜索结果正确性的同时，减小了搜索空间，进而提高算法效率。

ALT 方法是 Goldberg 等 [11] 在A* 算法基础上实现的算法。该方法首先在道路网络中选择若干个地标，计算网络中每个结点与地标之间的最短路径长度，将其作为启发信息预先存储。在最短路径查询时，利用结点与这些地标间最短路径长度及三角不等式估算搜索结点与终点之间最短路径的长度，使用结点与终点的最短路径长度作为 A* 算法搜索时的启发信息，从而实现对搜索空间的裁剪。

Reach 算法是指对于某一个结点 v，如果以 s 为起点、以 t 为终点的最短路径经过 v，v 在这条最短路径上的 Reach 可定义为最短路径上 s 到 v 与 v 到 t 的最小值。结点 v 可以根据网络中所有经过该点的最短路径计算出多个 Reach 数值，其中最大的一个数值就是 v

更多内容请查看pdf