中文摘要：

在道路网上计算两点之间的最短路径是图论算法的众多实际应用之一。经典的Dijkstra算法在大规模图上过于缓慢。过去十年间，这个经典问题在道路网上取得了重大突破，目前已知最快算法的运行效率比Dijkstra算法快了百万倍。这些算法都对道路网数据进行预处理，产生一定的辅助信息以加速查询，其中目标向导方法和层次化方法是两类典型方法。一些算法的实验性能良好，但缺乏理论支撑。这是因为难以用数学语言严格地刻画道路网的特性。因此，如何弥合理论与实践的差距是此问题面临的主要挑战。

英文摘要：

To compute exact point-to-point shortest path in road networks is one of numerous practical applications in graph algorithm. Classic Dijkstra’s algorithm has already turned out to be far too slow in large road networks. Over past decade this classical problem in road networks achieves significant breakthrough, the current known fastest algorithm has the operation efficiency one million faster than the Dijkstra’s algorithm. These algorithms all make pretreatment on the data of road networks, which brings about certain auxiliary information for speeding up the query. Among them there are two typical algorithms, the goal-directed approach and the hierarchical technique. Some of the algorithms have good performances in experimental studies, but the theoretical bounds are unknown to support these observation results. This is because it is hard to depict the characteristics of road networks strictly. Therefore it is the main challenge of the problem that how to fill the gap between the theories and the experimental results.