随着网络技术和经济的飞快发展,知识图谱在近年来悄然兴起,在各个重要领域广为应用,而在这些使用广泛的知识图谱应用中,最短路径的搜寻总是扮演着基石的角色并具有十分重要的意义,为图计算中不可避免的问题。随着图数据规模持续的增长,许多图数据集已经达到了千万级别的规模,并在可预见的未来将会越来越大,而计算机的计算能力却没有按同样速率增长,导致在单服务器下对最短路径距离的计算响应时间变得非常长,难以适应高并发的网络环境。因此,我们迫切需要寻找一种可适应分布式环境的新型算法来降低响应时间,来代替传统的Dijkstra一类的算法。为了解决这一有挑战的问题,本论文把最短路径计算简化为一个有界估计问题,即计算两点间的距离的上界限或下界限以得到距离的估计值,提出了一种新的距离估算算法,能够在数毫秒内在大型图数据集上估算出两点间的最短路径距离。近年来许多国外的研究者在最短路径的计算上都使用了“landmark选择”和最短路径树的框架,牺牲了部分精确度而获得了较高的响应速度。但是这些方法只能适应某一类型的图谱,没有很好的普适性。另一方面,它们在获得距离下界时表现不尽人意,而通过下界来计算两点间的距离却能更好的利用最短路径树的性质,并取得更加精确的结果。本课题来源于导师指导与个人兴趣,与导师共同商定。主要工作内容包括:(1)对相关技术的查阅和研究,提出了自己的landmark计算框架,以及一种对landmark的评价标准,这种计算框架能够良好的利用最短路径树的性质通过最短路径的下限来得到两点间距离的近似值。(2)本文提出了一种新颖的启发式landmark选择算法去选择出此评价标准下最优的landmark集合,并基于此landmark集合进行快速估算。(3)通过热门的分布式图处理系统来实现本文提出的距离估算算法,证明此算法有良好的水平扩展性,能够适应大规模并行式处理的系统或集群。(4)对数个典型的百万级别的不同类型真实图数据集进行了大量完备的实验,来保证方法的普适性。测试结果表明,本文提出的算法能在线上以毫秒级别的时间高效率地响应用户最短路径距离的查询,并能够得到优于其他同类算法的精确度,且在不同类型的数据集上能保持良好的稳定性。我们还将在后文提供用来进行测试的工程设计框架以供读者进行参考。