全点对的最短路径问题在社交网络,生物网络,网络路由处理中有着重要的应用,多数文献提出的方法是针对静态图的。然而在边及权值频繁变化的应用场景中,大量的重复计算会带来不必要的开销。为此许多研究将目光转向动态图的最短距离的研究,其中支持批量边的插入、删除的全点对最短距离的增量维护算法(All-Pairs Shortest Distances For Batch Insertions/Deletions Incremental Maintenance Algorithm,后面简称APSDs算法)是最新提出的高效算法。该算法基于磁盘,支持对大图(顶点数超过10000)的处理。APSDs算法需要以批量插入/删除的边集为基础迭代地扩展路径并计算相应距离,找到最短距离发生变化的点对(探测阶段)并更新其最短距离(更新阶段)。整个路径扩展是通过对图的(批量)层次遍历(BFS)实现的。所以随着图的的规模增加,算法的开销明显增大(每条插入/删除边层次遍历的时间复杂度达到(9)~2)),所以本文考虑在多线程环境下优化APSDs算法。基本并行划分思想和方法如下(具体划分要以保证算法的正确性为前提):(1)由于APSDs算法需要做批量BFS,如果对图本身做划分则要求是非连通图。而本文研究的图没有连通性的限制,所以考虑对算法中各个子过程(阶段)的输入数据做划分,最后在基于共享存储的并行计算模型上实现本并行算法。由于批量插入和批量删除在探测阶段对公共资源(全点对的最短距离)读写逻辑不同,本文为此给出不同的并行方法。(2)APSDs批量插入算法的并行方法:本文利用批量插入算法探测阶段对公共资源读写的局部性特征(在扩展路径和合并路径的点对的范围内)对整个迭代过程做并行,并在不同的应用场景下给出两种并行方案。(3)APSDs批量删除算法的并行方法:与(2)不同,本算法在探测阶段中对公共资源的读写不具备局部性,所以无法对整个迭代做并行,只能对每次迭代做并行执行。而更新阶段对公共资源的读写逻辑与(2)相似,可以对整个迭代做并行。最后在公开的数据集中验证了本文的并行算法,实验结果表明:(1)在图的规模较大的情况下有更好的加速效果;(2)加速比随着插入/删除边集的增大而增大,到达一定规模时趋于平缓。