在道路网上精确计算点对点最短路径是图论算法的众多实际应用之一。经典的Dijkstra算法及其变种双向Dijkstra搜索算法在大规模道路网上过于缓慢,早已力不从心。有幸的是在过去十年间,这个经典问题受到大量关注,尤其在大规模道路网上取得了极其重要的突破,目前很多算法的运行效率比Dijkstra算法快了好几个数量级。目标向导方法和层次化方法是两类最具代表性的方法,它们各自经历过一段快速发展时期。此外,将两类方法巧妙地结合起来能够在各方面都取得最佳效果。尽管实验表明这些算法性能良好,却缺乏理论分析的支撑。这是因为,道路网虽有一些性质,却无法严格地对它下定义。这些性质包括稀疏性、近乎可平面性以及层次化特性。然而,现有的算法大都只适应处理静态网络,它们需要较长的时间进行预处理,以产生足够的辅助数据来加速最短路径查询。因此,这些加速技术难以应付边权重经常变化的动态路网,诸如交通堵塞或者检修路况等,即使权重变化的边集只占整个路网的一小部分。鉴于现有的最快算法Transit-Node Routing,本文提出了相应的动态算法。我们仅更新受变化影响节点的辅助数据,避免了从头开始预计算。在实际应用中,边权重变化在累积到一定程度后才会对整个路网产生影响,我们的算法也能够利用这一特性进行批量更新。最后,我们对算法的预处理时间与空间开销,查询与更新运行时间等重要指标进行了实验评估。