1.一种求解大规模多段图最短路径的分布式方法，其特征在于：用|A|表示集合A中元素的个数；用 表示不大于a的最大整数，多段图是一个加权有向图G＝(V，E，W)，其中：(1) 是顶点集合，满足 其中Vi是第i个阶段的顶点集合，m为阶段个数；

(2)Vi＝{vi，j|j＝1，2，…，ni}，其中ni＝|Vi|，表示第i个阶段的顶点个数；

(3)E＝{|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是的权重；

(5)V1＝{v1，1}，Vm＝{vm,1}，v1，1和vm,1分别称为源点和汇点；

以c表示每个计算节点能够存储的边的最大数量；

具体步骤如下：

步骤1：执行如下步骤，对多段图进行划分：步骤1.1：取当前计算节点编号p＝1，当前边的总数量Sum＝0，循环变量i＝1，第p个计算节点CNp存储的第一个阶段编号sp＝i；

步骤1.2：取阶段i至阶段(i+1)的边集合Ei＝{|j＝1,2，…，ni；k＝1，2，…，ni+1}；

步骤1.3：取Sum＝Sum+|Ei|，若Sum＜c，则将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：对CNl中存储的第一个阶段的每个顶点 置步骤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；

步骤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；

步骤3.5：所有计算节点完成步骤3.4后，置 转步骤

3.2；

步骤3.6：计算节点CNp的顶点vm,1中所存储的SPLm，1即为结果，其中SPLm,1.Len是最短路径长度，SPLm,1.Path是最短路径。