全源最短路径是图计算的一个典型问题,它与描述复杂系统的最基本特征量——平均路径长度的求解密切相关,这为深入研究真实的复杂网络系统的基本构造与特征量奠定了基础。不仅如此,随着人类对生产与生活效率需求的增加,有关最短路径的问题越来越成为了不同专业的研究基础,为交通运输、旅行路径选取等问题提供了有效解决办法。因此,全源最短路径问题其具有重大的理论意义和很高的实用性。尽管求解最短路径的优化算法不断涌现,但随着图的规模急剧扩大,求解全源最短路径的困难也愈来愈大。对于大规模的图数据,单机的计算资源无法一次性承载其全源最短路径的计算任务,所以人们研究了若干分布式图计算系统,以实现针对大规模图数据的分布式计算。然而,分布式集群又意味着较高的成本,往往为普通用户所不可得。综上所述,研究一种单机系统下求解大规模图的全源最短路径的方法具有十分重要的意义。本文提出了一种求解大规模图的全源最短路径的分治策略,该策略将一个大图划分规模较小的子图,分别计算各子图的全源最短路径,并对子图的路径进行合并,从而得到整个图的全源最短路径。在该过程中,本文通过一个有效的图划分算法得到一个最优的顶点序列,按照该序列中的顶点顺序依次将图中顶点进行分割,最终能够以较少的分割点和较快的速度将一个大规模图进行划分。接着,在每个子图上使用改进的Dijkstra算法求出各自的全源最短路径,然后利用子图间相同的分割点将路径拼接起来,计算出整个图的全源最短路径结果。另外,本文还借鉴LRU策略的思想,对内存中的grid进行置换。本文提出的算法在真实的图数据集上行之有效,对于有限资源下求解规模较大图的平均最短路径和中心介数性提供了有效的方法,为研究网络的拓扑结构和解决实际问题提供了支持。