(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210278604.7 (22)申请日 2022.03.21 (71)申请人 北京化工大 学 地址 100029 北京市朝阳区北三环东路15 号北京化工大 学 (72)发明人 卢罡　刘艳伟　李睿琪　谷伟伟　 (74)专利代理 机构 北京太兆天元知识产权代理 有限责任公司 1 1108 专利代理师 王宇 (51)Int.Cl. G06Q 10/04(2012.01) G06F 16/36(2019.01) G06F 16/31(2019.01) (54)发明名称 有限资源下大规模图的全源最短路径分治 求解方法 (57)摘要 本发明公开了一种有限资源下大规模图的 全源最短路径分治求解方法， 首先将一个大图划 分为子图， 通过对子图逐一加载和计算得到部分 最短路径结果， 经过整合后得到全源最短路径结 果。 本发明提供的技术方案将一种新的分割算法 应用于图的分割， 通过这个算法能够得到一个顶 点序列， 按此序列对顶点进行删除时， 图会以较 少的分割点和较快的速度被分割成若干个子图， 通过对子图逐一加载和计算得到部分最短路径 结果， 经过整合后得到全源最短路径结果。 这个 方法不仅解决了单个机器上内存资源有 限的问 题， 而且还可以扩 展到分布式环境中。 权利要求书1页 说明书4页 附图2页 CN 114861970 A 2022.08.05 CN 114861970 A 1.一种有限资源下 大规模图的全 源最短路径分治求 解方法， 其特 征在于， 包括： 设置序列S， 初始时为空， 所述序列S表示删除顶点的顺序； 按照从小到大的顺序对图中的顶点度进行排序， 形成度 序列； 将所述点度最小的顶点 放入所述序列S； 在所述度序列中找出一个与 所述序列S中最后 一个元素没有连边的顶点放进所述序列 S， 依次进行， 直到所述度 序列中剩余的顶点全部与所述序列S中的顶点存在连边； 将所述度 序列中剩余的顶点按照所述度 序列的顺序放入所述序列S； 对所述序列S进行逆序得到最终顶点序列； 对图进行分割的过程中， 按照上述 顺序删除顶点， 直到 达到预设的分区数； 在划分后的子图上使用堆优化的迪克斯特拉算法获得最短路径； 对划分后的子图使用路径拼接算法进行整合， 获得整个图的全 源最短路径结果。 2.根据权利要求1所述的有限资源下大规模图的全源最短路径分治求解方法， 其特征 在于， 所述在划分后的子图上使用堆优化的迪克斯特拉算法获得最短路径的步骤 包括： 在算法初始时， 待排序的顶点以无序形式连续存放在一个一维数组中， 对所述待排序 的顶点按照距离源顶点远近进行堆 排序， 离源顶点近的顶点维护在堆顶， 形成小顶堆； 使用完全二叉树的顺序存储结构形式对各个顶点进行存储， 0号单元存放的是调整后 的堆顶元 素， 后面依次是左子树和右子树。 3.根据权利要求1所述的有限资源下大规模图的全源最短路径分治求解方法， 其特征 在于， 所述对划分后的子图使用路径拼接算法进行整合， 得到整个图的全源最短路径结果 的步骤包括： 计算第一个子图的全 源最短路径结果； 对于与第一个子 图有边界点的邻接子 图， 其与第一个子 图共享边界点， 通过边界点将 两个子图中的之间的路径连接起 来， 得到两个子图所有顶点间的最短路径； 使用剩余的子图继续更新路径， 直到获得整个图的全 源最短路径结果。权　利　要　求　书 1/1 页 2 CN 114861970 A 2有限资源下大规 模图的全 源最短路径分治求 解方法 技术领域 [0001]本发明涉及复杂网络的最短路径的技术领域， 尤其涉及 一种有限资源下大规模图 的全源最短路径分治求 解方法。 背景技术 [0002]全源最短路径(All  Pairs Shortest Paths， APSP)问题旨在寻找网络图中所有顶 点之间的最短路径。 随着信息技术的发展， 最短路径问题已成为各个学科中不可或缺的理 论。 它是图平均最短路径长度和介数中心性问题的基础， 是衡量图的拓扑结构和图的顶点 或边的重要性的重要指标。 但是， 随着图的越来越 大， APSP的计算会消耗越来越多的计算机 资源， 例如内存和CPU时间。 [0003]为了应对海量图数据的挑战， 设计支持横向扩展的分布式图计算系统来进行分布 式集群上并行运算是目前最主流的一个解决方案。 与传统的大数据处理系统(如 MapReduce、 Spark等)不同， 这些专用的图计算系统针对图的数据结构进行了优化， 保持了 系统的可扩展性。 然而， 分布式集群对部 分用户来说代价过高， 直接在一台机器上计算大型 图的APSP， 可能会因为资源消耗过 大而导致机器崩溃。 发明内容 [0004]为解决现有技术存在的局限和缺陷， 本发明提供一种有限资源下大规模图的全源 最短路径分治求 解方法， 包括： [0005]设置序列S， 初始时为空， 所述序列S表示删除顶点的顺序； [0006]按照从小到大的顺序对图中的顶点度进行排序， 形成度 序列； [0007]将所述点度最小的顶点 放入所述序列S； [0008]在所述度序列中找出一个与所述序列S中最后一个元素没有连边的顶点放进所述 序列S， 依次进行， 直到所述度 序列中剩余的顶点全部与所述序列S中的顶点存在连边； [0009]将所述度 序列中剩余的顶点按照所述度 序列的顺序放入所述序列S； [0010]对所述序列S进行逆序得到最终顶点序列； [0011]对图进行分割的过程中， 按照上述 顺序删除顶点， 直到 达到预设的分区数； [0012]在划分后的子图上使用堆优化的迪克斯特拉算法获得最短路径； [0013]对划分后的子图使用路径拼接算法进行整合， 获得整个图的全 源最短路径结果。 [0014]可选的， 所述在划分后的子图上使用堆优化的迪克斯特拉算法获得最短路径的步 骤包括： [0015]在算法初始时， 待排序的顶点以无序形式连续存放在一个一维数组中， 对所述待 排序的顶点按照距离源顶点远近进行堆 排序， 离源顶点近的顶点维护在堆顶， 形成小顶堆； [0016]使用完全二叉树的顺序存储结构形式对各个顶点进行存储， 0号单元存放的是调 整后的堆顶元 素， 后面依次是左子树和右子树。 [0017]可选的， 所述对划 分后的子图使用路径拼接算法进行整合， 得到整个图的全源最说　明　书 1/4 页 3 CN 114861970 A 3