技术摘要： 本发明公开了一种求解大规模多段图最短路径的分布式方法，属于计算机技术领域。包括如下步骤：多段图划分；各部分子图求部分最短路径；各计算节点通信求多段图最短路径。本发明相较于单机求解算法，能够使用分布式系统处理更大规模的多段图数据；相较于已有的分布式求 全部
背景技术：
最短路径问题是图论中的一个经典问题，旨在寻找图中一对顶点之间的最短路
径。多段图是一类特殊的加权有向图，图中的顶点分为至少两个不相交的集合(称为阶段)，
其中第一个和最后一个阶段有且仅有1个顶点，分别称为源点和汇点，图中边只能从前一阶
段的顶点指向后一阶段的顶点。很多工程应用中的实际问题都可以建模为多段图，所以其
应用十分广泛。
随着多段图规模的不断增大，单机算法既无法存储所有的多段图数据，也无法实
现最短路径的求解。此时，分布式算法成为必选。
分布式算法是将图数据尽量均衡地分配到计算机集群的计算节点上，然后各个计
算节点并行计算本机上结果，再汇总各个部分结果得到最终结果。目前，已经提出了并行
Dijkstra算法、并行Floyd算法、基于ball string模型的并行算法、Δ-Stepping并行算法
等，这些方法虽然也适用于于多段图，但是没有充分利用多段图的特点，通信量过大，计算
效率低。
技术实现要素：
针对现有技术中存在的上述技术问题，本发明提出了一种求解大规模多段图最短
路径的分布式方法，设计合理，克服了现有技术的不足，具有良好的效果。
为了实现上述目的，本发明采用如下技术方案：
一种求解大规模多段图最短路径的分布式方法，用|A|表示集合A中元素的个数；
用 表示不大于a的最大整数，多段图是一个加权有向图G＝(V,E,W)，其中：
(1) 是顶点集合，满足 其中Vi是第i个阶段的顶点
集合，m为阶段个数；
(2)Vi＝{vi,j|j＝1,2,…,ni}，其中ni＝|Vi|表示第i个阶段的顶点个数；
(3)E＝〈{ vi,j,vi 1,k>|i＝1,2,…,m-1；j＝1,2,…,ni；k＝1,2,…,ni 1}是边集合；
(4)W＝{wi ,j ,i 1 ,k|i＝1,2,…,m-1；j＝1,2,…,ni；k＝1,2,…,ni 1}是权重集合，
wi,j,i 1,k是〈vi,j,vi 1,k〉的权重；
(5)V1＝{v1,1}，Vm＝{vm,1}，v1,1和vm,1分别称为源点和汇点；
以 表示每个计算节点能够存储的边的最大数量；
具体步骤如下：
步骤1：执行如下步骤，对多段图进行划分：
步骤1.1：取当前计算节点编号p＝1，当前边的总数量Sum＝0，循环变量i＝1，第p
个计算节点CNp存储的第一个阶段编号sp＝i；
5
CN 111552844 A 说 明 书 2/7 页
步骤1.2：取阶段i至阶段(i 1)的边集合Ei＝{
|j＝1,2，…，ni；k＝1,
2，…，ni 1}；
步骤1.3：取Sum＝Sum |Ei|，若 则将Ei中所有边分配到计算节点CNp中，取
CNp存储的最后一个阶段ep＝i 1，并继续下一步，否则转步骤1.5；
步骤1.4：取i＝i 1；若i≤m-1，转步骤1.2，否则转步骤2；
步骤1.5：取Sum＝0，p＝p 1，sp＝i，转步骤1.3；
步骤2：第l个计算节点CNl(l＝1，2，…，p)执行如下步骤求各部分子图的部分最短
路径，即所有计算节点并行执行如下步骤：
步骤2.1：对CNl中存储的每个顶点vi，j(i＝sl，sl 1，…，el，j＝1，2，…，ni)，用
表示顶点 到顶点vi，j的最短路径距离，用 表示顶点 到顶点vi，j的最短路径上，
vi，j的前驱顶点在第(i-1)个阶段的序号；
步骤2 .2：对CN l中存储的第一个阶段的每个顶点 置
步骤2.3：取循环变量i＝sl；
步骤2.4：置i＝i 1，若i≤el，即CNl中存储的最后一个阶段的编号，转下一步，否则
转步骤2.11；
步骤2.5：取循环变量j＝0；
步骤2.6：置j＝j 1，若j≤ni，即不大于Vi中最后一个顶点的编号，转下一步，否则
转步骤2.4；
步骤2.7：取循环变量k＝0；
步骤2.8：置k＝k 1，若 即不大于 中最后一个顶点的编号，转下一步，否
则转步骤2.6；
步骤2.9：取
步骤2.10：取 其中vi-1，q是 所对应的顶点，转步骤
2.8；
步骤2.11：用 表示顶点 到顶点 的最短路径。取循环变量i＝0；
步骤2.12：置i＝i 1，若 即不大于 中最后一个顶点的编号，转下一步，否
则转步骤2.18；
步骤2.13：取循环变量j＝0；
步骤2.14：置j＝j 1，若 即不大于 中最后一个顶点的编号，转下一步，否
则转步骤2.12；
步骤2.15：取循环变量k＝i，循环变量h＝el，
步骤2.16：若h≠sl，转下一步，否则转步骤2.14；
6
CN 111552844 A 说 明 书 3/7 页
步骤2.17：取 h＝h-1， 转步骤2.16；
步骤2.18：CNl中存储的第el阶段的每个顶点 产生一个最短路
径信息列表 其中Lenj
和Pathj分别表示 到 的最短路径的长度和路径；
步骤3：执行如下步骤，通过各计算节点通信来求多段图最短路径：
步骤3.1：参与通信的计算节点编号集合R＝{1，2，…，p}；
步骤3.2：若|R|＞1，转下一步，否则转步骤3.6；
步骤3.3：每个计算节点 将
发送给计算节点
步骤3.4：每个计算节点 执行如下步骤：
步骤3.4.1：取循环变量k＝0；
步骤3.4.2：置k＝k 1，若 即不大于 中最后一个顶点的编号；置临时
变量 即空集，转下一步，否则转步骤3.5；
步骤3.4.3：取循环变量j＝0；
步骤3.4.4：置j＝j 1，若 即不大于 中最后一个顶点的编号，转下
一步，否则转步骤3.4.10；
步骤3.4.5：取循环变量g＝0；
步骤3.4.6：置g＝g 1，若 转下一步，否则转步骤3.4.4；
步骤3.4.7：取循环变量h＝0；
步骤3.4.8：置h＝h 1，若 转下一步，否则转步骤3.4.6；
步骤3.4.9：若 的最后一个顶点与 的第一个顶点
相同，置
转步骤3.4.8；
步骤3.4.10：置 取循环变量g＝0；
步骤3.4.11：置g＝g 1，若 即不大于 中最后一个顶点的编号，转
下一步，否则转步骤3.4.2；
步骤3.4.12： 其中
且为以 为起点、以 为终点的所有路径的最短路径，转步骤3.4.11；
7
CN 111552844 A 说 明 书 4/7 页
步骤3.5：所有计算节点完成步骤3.4后，置 转步
骤3.2；
步骤3.6：计算节点CNp的顶点vm，1中所存储的SPLm，1即为结果，其中SPLm,1.Len是最
短路径长度，SPLm,1.Path是最短路径。
本发明所带来的有益技术效果：
(1)相较于单机求解算法，此算法能够使用分布式系统处理更大规模的多段图数
据。
(2)相较于已有的分布式求解算法，满足负载均衡的要求并最小化通信开销。
附图说明
图1为本发明方法的流程图。
图2为多段图划分阶段子流程图。
图3为求多段图部分最短路子流程图。
图4为各计算节点通信子流程图。
图5为多段图实例图。
图6为多段图划分结果示意图。
