[發明專利]一種求解大規模多段圖最短路徑的分布式方法

有效

• 申請號: 202010329809.4
• 申請日: 2020-04-24
• 公開（公告）號: CN111552844B
• 公開（公告）日: 2023-07-04
• 發明（設計）人: 崔煥慶;劉瑞雪;許少華;張峰;魏永山;徐強
• 申請（專利權）人: 山東科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06Q10/047
• 代理公司: 青島智地領創專利代理有限公司 37252
• 代理人: 種艷麗

1.一種求解大規模多段圖最短路徑的分布式方法，其特征在于：用|A|表示集合A中元素的個數；用表示不大于a的最大整數，多段圖是一個加權有向圖G＝(V，E，W)，其中：

(1)是頂點集合，滿足其中V_i是第i個階段的頂點集合，m為階段個數；

(2)V_i＝{v_i，j|j＝1，2，…，n_i}，其中n_i＝|V_i|，表示第i個階段的頂點個數；

(3)E＝{v_i，j，v_i+1，k|i＝1，2，…，m-1；j＝1，2，…，n_i；k＝1,2，…，n_i+1}是邊集合；

(4)W＝{w_{i，j，i+1，k}|i＝1,2，…，m-1；j＝1，2，…，n_i；k＝1，2，…，n_i+1}是權重集合，w_{i，j，i+1，k}是v_i，j，v_i+1，k的權重；

(5)V₁＝{v_1，1}，V_m＝{v_m,1}，v_1，1和v_m,1分別稱為源點和匯點；

以c表示每個計算節點能夠存儲的邊的最大數量；

具體步驟如下：

步驟1：執行如下步驟，對多段圖進行劃分：

步驟1.1：取當前計算節點編號p＝1，當前邊的總數量Sum＝0，循環變量i＝1，第p個計算節點CN_p存儲的第一個階段編號s_p＝i；

步驟1.2：取階段i至階段(i+1)的邊集合E_i＝{v_i，j，v_i+1，k|j＝1,2，…，n_i；k＝1，2，…，n_i+1}；

步驟1.3：取Sum＝Sum+|E_i|，若Sum＜c，則將E_i中所有邊分配到計算節點CN_p中，取CN_p存儲的最后一個階段編號e_p＝i+1，并繼續下一步，否則轉步驟1.5；

步驟1.4：取i＝i+1；若i≤m-1，轉步驟1.2，否則轉步驟2；

步驟1.5：取Sum＝0，p＝p+1，s_p＝i，轉步驟1.3；

步驟2：所有計算節點并行執行如下步驟求所存儲子圖的部分最短路徑，對第l個計算節點CN_l(l＝1，2，…，p)，步驟如下：

步驟2.1：對CN_l中存儲的每個頂點v_i,j(i＝s_l，s_l+1，…，e_l，j＝1,2，…，n_i)，用表示頂點到頂點v_i,j的最短路徑長度，用表示頂點到頂點v_i，j的最短路徑上，v_i，j的前驅頂點在第(i-1)個階段的編號；

步驟2.2：對CN_l中存儲的第一個階段的每個頂點置

步驟2.3：取循環變量i＝s_l；

步驟2.4：置i＝i+1，若i≤e_l，即不大于CN_l中存儲的最后一個階段的編號，轉下一步，否則轉步驟2.11；

步驟2.5：取循環變量j＝0；

步驟2.6：置j＝j+1，若j≤n_i，即不大于V_i中最后一個頂點的編號，轉下一步，否則轉步驟2.4；

步驟2.7：取循環變量k＝0；

步驟2.8：置k＝k+1，若即不大于中最后一個頂點的編號，轉下一步，否則轉步驟2.6；

步驟2.9：取

步驟2.10：取其中v_i-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＝e_l，

步驟2.16：若h≠s_l，轉下一步，否則轉步驟2.14；

步驟2.17：取h＝h-1，轉步驟2.16；

步驟2.18：CN_l中存儲的第e_l階段的每個頂點產生一個最短路徑信息列表其中Len_j和Path_j分別表示到的最短路徑的長度和路徑；

步驟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：計算節點CN_p的頂點v_m,1中所存儲的SPL_m，1即為結果，其中SPL_m,1.Len是最短路徑長度，SPL_m,1.Path是最短路徑。