陆文琦，谷远利，李萌，王硕，张源

(北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京 100044)

随着计算机和地理信息技术的快速发展，智能导航与位置查询服务在辅助人们出行方面发挥出越来越重要的作用，尤其是车载导航系统正逐渐成为所有驾驶人员的必备产品。但是由于城市汽车保有量的不断攀升，道路网络规模不断增大，交通情况愈发复杂，用户急需更加高效、准确的最短路径算法以获取动态灵活的导航服务。

最短路径算法被广泛应用于车辆诱导、交通流分配等领域，最早用来解决点到点最短路径的算法是经典Dijkstra算法[1]，Bellman-Ford算法和Floyd算法也被用来解决过此类问题。Hart等[2-3]在经典Dijkstra算法基础上提出了A*算法，该算法利用当前点到目标点的最短路径长度的估值更快地向目标点靠近，始终根据既定的规则，通过不断扩大“最有希望”[4]的节点集合进行探索，由于在搜索过程中省略大量无谓的搜索路径，比Dijkstra算法的效率更高。与A*算法类似，Pearl等[5]提出了Weight A*算法(简称WA*)，在计算路径时，A*算法和WA*算法均以两点间直线距离作为最短路径长度估值，WA*求解得到的路径质量与其算法运行时设置的参数有关，可以在大规模网络上找到一条与标准最短路径相差不大的路径。

以上算法主要以标号法为主，没有对图进行预处理。针对大规模网络计算时间长、占用内存空间大、无法应对快速查询的缺陷，在传统算法的基础上逐步形成了基于预处理的最短路径算法，包括预处理阶段和路径查询阶段[4]。……