计算公路网络中两点之间的最短路径问题,由于其在很多地图服务和商业导航系统中有着广泛的应用,最近重新引起了大家的关注。当前的加速方法主要是基于预计算技术,大致可以分为两类：基于空间一致性的最短路径加速方法和基于点重要性的最短路径加速方法,它们和经典的Dijkstra方法相比,均有显著的提高。但是这两类算法由不同的研究者提出,同时他们之间的工作并没有相互引用过,两类算法也没有在同一实验平台上进行系统的比较过,这导致用户在具体的应用条件下并不知道该如何选择合适的方法。此外,当前的算法自身在进行实验评价时还存在以下问题：有些方法仅仅在包含10万点规模的小型公路网络上测试过；有些方法在查询时只强调最短距离(而不是最短路径查询),即只返回两点之间的最短路径的长度；还有一种方法在实验中的实现方法是错误的,将导致不正确的查询结果。为了解决以上的问题,本文对当前最具代表性的基于空间一致性的加速方法和基于点重要性的加速方法从理论和实验方面进行了详细的比较,并且在基于空间一致性方法的基础上,提出了一种新的数据结构最短路径B+树,它能够更有效的存储预先计算好的最短路径信息,完善了当前的工作。在实验中通过使用最大包含两千万点的真实公路网络,从预处理时间,空间花销和查询效率(包括最短距离和路径查询)等各个方面对两类算法进行了详细的分析比较。实验结果说明了每种算法的特性以及优缺点,根据这些可以在不同的应用情况下选择出最合适的方法。