最短路径算法是算法中的经典算法之一。最短路径算法不仅可以用来解决计算机方面的问题,还可以用来解决优化道路规划、传感器部署等很多现实问题。节点边介数的计算,中心点的寻找,社区的发现、商品的推荐等一系列复杂网络相关问题的分析与研究都需要用到最短路径算法。随着社会发展,应用最短路径算法的图的规模越来越大,经典的Dijkstra和Floyd最短路径算法早已经不适用于相关的计算。经典算法的复杂度太高,计算量较大,需要空间大,在大数据的处理方面能力不足。因此为克服这些难点,超大规模图的最短路径近似算法应运而生,其中基于区域划分的中心距离的最短路径长度近似算法(简称CDZ算法)和基于坐标的Orin算法(简称Orin算法)最有代表性。CDZ算法在复杂网络的计算中运算效率较高,Orin算法的准确率较高但在预处理方面运算量较大。根据对社交网络这类复杂网络的研究,统计领域的研究者们发现超大规模网络中存在许多特性。这些网络特性的发现有利于超大规模图的最短路径算法的优化。因此我们在已有算法的基础上提出了新的算法,主要研究工作及成果如下：1)通过研究分析复杂网络,一些基本的网络模型和复杂网络的特征统计量找到能够急遽收缩超大规模网络的方法。通过研究分析经典最短路径算法和已有的大规模图的最短路径近似算法,找出其算法的优点和不足,寻找改进的突破口。2)根据超大规模图的自相似特性提出基于缩略网络的最短路径近似算法。通过构造缩略网络高效地降低网络规模,缩短预处理时间。算法充分利用复杂网络的自相似特性对节点收缩,在粗粒度下的网络和细粒度的网络具有相似性,收缩后的网络性质与原网络一致。在对网络进行预处理之后,运用公式计算节点间最短路径长度的近似值。3)在构建缩略网络计算出最短路径近似长度的基础上,通过最短路径上landmark规模来近似经过该节点的最短路径数目,再根据公式计算出被收缩及节点的介数值。计算出图中所有介数值之后再通过公式计算出各节点对应的介数中心性。4)通过不同规模的数据集将算法与其他算法进行对比分析,验证算法的优劣。5)用WindowBuilder Pro插件实现最短路径近似距离Oracle,程序包含预处理、最短路径近似距离查询和介数计算三个部分。由实验结果得出,本文提出的算法在超大规模网络中相较于其他算法,运算效率有所提高且准确率仍保持较高水平。在超大规模图中,处理百万节点和千万条边本文算法只需要几十毫秒,这一运算效率是CDZ算法的数十倍,远高于Orin算法。在介数中心性的计算方面,本文算法也优于UB算法和CDZ中心性算法,算法运行效率提高数倍,准确率略有下降。