康瑞部落

一、介绍

最短路查询算法是图论中的经典算法，被广泛地应用在不同场景，例如计算机网络中的路由算法。在时空场景下，最短路算法更是支撑了很多应用，例如在路径规划和推荐中最短路是一种最直接的方案，而目前主流的基于隐马尔科夫模型的轨迹地图匹配算法也会产生大量的最短路查询 [1]。具体如图1所示，在计算相邻两个轨迹点之间可能的匹配路段时，地图匹配算法会首先做一个范围查询确定候选路段，为了计算候选路段之间的转移概率，地图匹配算法会对两个候选集合所有路段两两之间做最短路查询。然而，这些实际应用中的图往往规模巨大，未经优化的传统最短路算法会带来严重的效率问题。

下面，本文将首先分析经典的最短路算法在大规模图上会产生的问题，接着介绍一些优化方案，并简要地总结其背后的思想。

图1地图匹配算法涉及的最短路查询

二、经典的最短路查询算法

经典的最短路算法包括Bellman-Ford，迪杰克斯拉和A*算法等。Bellman-Ford算法对图进行松弛操作，得到所有可能的最短路径，但是其时间复杂度达到了O(VE)。迪杰克斯拉算法维护一个到出发点距离排序的优先队列，每一步迭代同样对节点进行松弛操作，其复杂度会受使用的优先队列算法影响，如使用二元堆其时间复杂度为O((|V| + |E|)log|V|)，优化的斐波那契堆能使其复杂度降到O(|E| + |V|log|V|)。然而当前城市路网的节点和边的数量往往在几万和几十万的量级，这样的复杂度显然难以满足在实际路网上的需要进行大规模最短路查询的应用。迪杰克斯拉算法的一个主要问题是，对于一个只需要计算两点间最短路的应用，往往会产生较大的搜索空间。因而，一些方法尝试优化其搜索空间，例如使用双向的迪杰克斯拉算法如图2所示。另一种经典的最短路算法是A*算法，其使用了一种启发式函数来估计节点到终点的距离，从而使得期望距离小的节点优先被搜索，如果使用的启发式函数能够确保估计的距离小于真实的距离那么这种A*算法能够确保找到真实的最短路。优化的搜索空间如图2中最右边所示。路网上一种可行的启发式函数是两点间的直线距离，因为在路网上从一处到另一处所需的行驶距离总是小于等于其真实距离的。然而这种启发式函数对于实际路网来说只能提供一个较弱的bound[2]，仍然难以支撑大规模的应用。

图2经典最短路算法搜索空间的优化（左图为迪杰克斯拉算法，中图为双向迪杰克斯拉算法，右图为A*算法）

可以看出，经典的最短路查询算法只适用于小规模图上的查询，一些优化方案虽然一定程度减少了搜索空间但在真实路网的场景下，仍然难以满足实际应用的需求。

三、进阶的最短路算法

单纯的优化算法本身很难进一步优化最短路查询在真实路网上的效率，为了解决这个挑战，进阶的最短路算法都会预计算一些路网图的信息进行存储，在查询时这些预计算的信息或是为搜索提供更强有力的剪枝或是直接通过查表的方式得到结果。这一部分将介绍四种进阶的最短路算法。

3.1 Contraction Hierarchies

Contraction Hierarchies[3]算法的大体思想是，在预计算阶段在原始的图上加上一些“捷径”，并给图上每个节点赋予一个级别值，在做最短路计算时，会根据节点级别进行搜索并走捷径从而极大的剪枝搜索空间。

具体地，在预处理阶段，CH算法每一步会选择一些节点进行“收缩”（删除），如果这个节点的删除会影响到相邻节点之间的最短路访问，那么一条“捷径”会添加到这相邻的两个节点，捷径的权重就是原先相邻节点间实际最短路的大小。每一步“收缩”的节点会被赋予一个级别值，越在后收缩的节点级别越高。图3给出了一个例子，在这个图中黑色实线部分是原始图中存在的边且默认权重为1，假设先收缩左上的紫色节点，这个节点的删除会导致其相邻节点之间的最短路会从2变为正无穷，所以三条紫色虚线代表的“捷径”会加入其中。在之后的搜索过程中，如果计算相邻节点的最短路时，会直接走捷径而不是通过节点1。这一阶段会收缩完图上的所有节点。

图3CH算法收缩阶段示例

在搜索阶段，CH算法会从最短路起点和终点分别进行迪杰克斯拉搜索，但是从起点开始的搜索和从终点开始的搜索都要求每次只选择比当前节点级别高的节点加入优先队列。搜索阶段中，双向搜索都遵循只能找更高级别节点进行搜索的原则，但可能会出现多个结果如图4所示，这时取所有可能的结果中路径最短的作为最终结果。

图4CH算法搜索阶段，截取自[4]

CH算法一个重要的问题是节点收缩的顺序，这里一个选择原则是，尽可能选取收缩后需要添加较少“捷径”的节点优先收缩。实际实现中，一般会使用一些启发式的方法决定先后顺序，关于CH算法更多细节可以参考原文[3]和一篇教程[5]。

3.2 A*的优化：ALT

前面提过，基于空间直线距离的启发式函数在路网上的表现不佳。那么为A*算法设计一种更优的启发式函数也是一个可行的优化方案，ALT (A*, landmarks, and triangle inequality)算法[6]是其中的一种。在预处理阶段，ALT算法会选择节点集合中的一个小的子集合，并计算子集合每个节点到所有其他节点的最短距离。在最短路搜素时，如图5中，可以通过三角不等式的思想得到A*的启发式函数，如需要估计d(u, t)时，通过预计算已知d(u, li)和d(t,li)那么根据三角不等式d(u,t) + d(t,li) <= d(u, li)即d(u, t)<= d(u, li) - d(t,li)，再在所有L集合中找到使得d(u,t)上界最大的。这种启发式函数往往比基于空间距离的启发好很多。

图5 ALT算法示例

3.3 Compressed Path Databases

CPD是一种在查询阶段最快速的最短路查询算法，但相应的会有很高的预计算和存储开销。这种方法在预处理阶段会计算所有节点之间的最短路。为了减少存储开销，每个节点会记录到其他节点的最短路距离和到达对应节点行走的第一步，搜索时得到第一步信息后再在新的节点进行查询下一步的走法。这样，单纯通过查表的方式就能完成最短路的搜索，不会有更大的搜索空间。这种方法可以做到比其他方式快得多的查询，但是缺点也十分明显，即需要更多的存储开销和预计算的过程。

3.4 性能比较

除了以上介绍的3种算法，大规模路网上的最短路计算还有很多方案，这里不一一列举，感兴趣的读者可以进一步参考[2]中的介绍。一个重要衡量指标是预计算量、存储开销和加速效果的tradeoff。[6]中给了不同算法的一个性能和开销比较如图6所示。

图6不同进阶最短路算法开销和加速情况

其中XT一列指的是预计算耗时的量级，XM一列是存储开销的量级，Query Time则是最短路计算时搜索时间的量级。可以明显看出，加速效果越好的算法需要更大的预计算与存储开销。

这些算法各有优劣具体使用时需要根据面临的应用进行分析，例如在一些地图厂商的场景下，除了最短路搜索速度，还要考虑路网更新时预计算信息的及时更新，所以会选择一些Cell based Routing方式[7]，而介绍中提到的轨迹地图匹配场景下，需要做最短路计算的轨迹点之间距离往往很近，预计算时只需要计算每个节点到一定空间范围内节点的最短路。所以一些追求性能的工作也会选择基于Compressed Path Database的方法[8]。

四、总结

本文主要介绍了最短路算法在城市级别路网上的一些优化方案，从经典算法出发，分析其遇到的性能挑战，并介绍了三种现有的方案，最后给了相应的实验对比。实际应用中需要根据实际面对的问题对最短路优化技术进行选择和调优。

引用

[1] Newson, Paul, and JohnKrumm. "Hidden Markov map matching through noise andsparseness." Proceedings of the 17th ACM SIGSPATIAL internationalconference on advances in geographic information systems. 2009.

[2] Bast, Hannah, et al. "Route planning intransportation networks." Algorithm engineering. Springer,Cham, 2016. 19-80.

[3] Geisberger,Robert, et al. "Exact routing in large road networks using contractionhierarchies." Transportation Science 46.3 (2012):388-404.

[4]ICAPS 2018: Hannah Bast on "Route Planning in LargeTransportation Networks: Surprisingly Hard ...“https://www.youtube.com/watch?v=B3wKfJAVRkg

[5]https://fmi.uni-stuttgart.de/files/alg/teaching/s15/alg/CH.pdf

[6] IJCAI 18 Tutorial：An Introduction to Contraction Hierarchies.  https://movingai.com/IJCAI18-HS/ijcai-hs-harabor.pdf

[7] 高德地图：AI在出行场景的应用实践：路线规划、ETA、动态事件https://mp.weixin.qq.com/s/8w5tjkT1jAUAca0tH9CJHw)

[8] Yang, Can, and Gyozo Gidofalvi. "Fast mapmatching, an algorithm integrating hidden Markov model withprecomputation." International Journal of Geographical InformationScience 32.3 (2018): 547-570

关注公众号，订阅更多内容