最短路径问题是图论和算法设计中的经典问题。也是现实世界的许多应用中的基本问题,如路径规划、物流规划、GPS导航、生物医学、社交网络、基于位置的服务(LBS)等等。尽可能快地计算最短路径是这些应用的迫切需求。随着GPS、电子地图和LBS的发展,位置信息爆炸式增长,图的规模也越来越大。传统算法已经无法满足实时性的需求,特别是在基于路网的应用中。与此同时,这些应用需求也在不断推动最短路径算法的持续发展。尽管对最短路径算法的研究已经取得了突飞猛进的发展,但是面对数据规模的迅速增长和实时性要求的日益普遍,目前的算法仍然面临巨大的挑战。应对挑战的方法一般有三：①研究更高效的串行算法：预处理技术是解决这个问题的有效方法。②研究近似算法：在大多数现实场景中没有必要计算精确距离。使用近似距离可以有效的降低计算的复杂度。③研究并行算法：为了充分利用现代多核体系结构的特性,开发并行算法是必然选择。围绕提高最短路径算法的性能这一目标,本文沿两条线索展开研究工作：以最短路径问题的分类为线索,本文研究了单源最短路径、点到点的最短路径和全源最短路径问题；以未来的研究趋势为线索,本文提出了新的串行、近似和并行算法。具体来说,本文的主要研究成果、贡献和创新点可以概括为以下几点：(1)提出求解点到点的最短路径的高效下界算法。在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题。学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等。这些算法使用的距离估值比较松散,仍然有很大的提升潜力。本文提出了一种新的两阶段目标制导下界算法ACT算法。它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识。新算法充分利用了预处理数据,可以获得非常好的距离下界。在真实路网上的实验结果表明,新算法的性能明显优于以往的算法。在某些实例下,ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25%左右。(2)提出在路网上检索k近邻的基于预处理的近似算法。路网上的k近邻检索已经引起越来越多的学者的关注。本文提出了一种简单高效的预处理算法检索近似k近邻。算法选取顶点集合V的一个子集R作为代表顶点,计算R中所有顶点对之间的最短路径距离。因为|R|≤|V|,算法只需要较少量的内存空间,kNN检索系统可以部署在普通的桌面级计算机上。而且,算法中使用的是误差可控的近似距离。实验表明,误差上限较小时,近似算法的检索结果比较精确。(3)优化OpenCL异构计算平台上的并行单源最短路径算法。由于数据相关性较强,很难直观地并行化传统的最短路径算法。异构计算为解决这一难题带来了机遇和挑战。本文讨论了OpenCL的内存一致性,研究了已有的并行算法,并提出了一个改进型算法。通过调整数据结构和使用原子操作,改进后的算法大大减少了内核调用的次数。实验结果表明,改进版本的性能比原始版本提高了一倍多。(4)优化大规模稀疏图上的全源最短路径算法。在大规模稀疏图上计算全源最短路径的主流方法仍然是重复调用Dijkstra算法。本文研究了标号初值与标号修正算法性能之间的关系,提出了利用增量计算初始化标号数组的优化方法,大大减少了顶点重入次数。实验结果表明,改进算法的性能比原算法提高了约一个数量级。