点到点的最短路径问题是复杂网络和GIS等学科中的经典问题,在实践中得到广泛应用,如物流运输、车载导航、社交网络、计算机网络等。虽然针对该问题提出过许多经典算法,但是随着网络规模迅速扩大,网络拓扑结构越来越复杂,对现有的最短路径算法提出新的挑战。多核计算机的出现,为最短路径搜索算法的改进提供新途径。本文主要内容如下:首先,对最短路径的研究背景和意义、国内外研究进展进行总结,介绍了本文的研究内容、组织结构及技术路线。其次,对当前点到点的最短路径算法进行分类总结,包括精确最短路径算法、近似最短路径算法。精确最短路径算法,如Dijkstra、BFS、SPFA、Bellman-Ford等,该类算法常应用于精度要求较高的情形,如计算机网络协议、数据库查询等;近似最短路径算法,如A*、双向算法、分层算法、ALT等,该类算法应用在对精度要求不太高的情形,如机器人导航、地图导航等。其次,对树分解算法进行分类总结,主要包括两类:基于消除序列的树分解算法和基于割集的树分解算法。基于消除序列的树分解算法主要有弦图识别算法,如:最大基搜索泛(Maximum Cardinality Search algorithm)、字典广度优先搜索算法(Lexicographic Breadth First Search algorithm)等,基于贪心的三角化算法,如:基于最小度的树分解算法(MinDegree)、基于最小填充的树分解算法(MinFill)等,基于剪枝约束的算法等,该类算法主要特点是时间复杂度较低。基于割集的树分解算法主要有基于组件分割策略的算法(The splitting into components strategy)、基于最小顶点割集的启发式算法(The Minimum Separating Vertex Sets heuristic)等,该类算法的优点是可以根据树分解的上界作为启发,但是时间复杂度较高。然后,通过对HTEDI算法(由Fang Wei-Kleiner于2016年提出)的分析。据此对最短路径查询过程进行改进,主要包括,将算法的查询过程从双向计算过程改为单向,使算法在有向图中也是可靠解;将根节点的计算过程进行特殊处理(见第五章),保留原算法时间和空间平衡的优点;根据树分解父节点和子节点的特点,加快最短路径算法的查询过程。在真实的道路网中进行实证分析,证明改进后的算法在有向有权图上是可靠解,并且查询速度得到有效改善。接着,考虑到树分解方法的选择可能会影响HTEDI算法的效率。第五章详细对比MinFill的树分解方法和MinDegree的树分解方法,将MinFill的树分解方法应用于HTEDI算法,与采用MinDegree的HTEDI算法进行对比,通过实验分析,证明采用MinFill比采用MinDegree方法在预处理部分的时间和空间上的结果都要好,同时最短路径查询计算速度得到提高。最后,本文给出了相关的结论,并对未来的工作进行展望。