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

有效

• 申請?zhí)枺?/td>: 202010329809.4
• 申請日: 2020-04-24
• 公開（公告）號: CN111552844B
• 公開（公告）日: 2023-07-04
• 發(fā)明（設(shè)計）人: 崔煥慶;劉瑞雪;許少華;張峰;魏永山;徐強(qiáng)
• 申請（專利權(quán)）人: 山東科技大學(xué)
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06Q10/047
• 代理公司: 青島智地領(lǐng)創(chuàng)專利代理有限公司 37252
• 代理人: 種艷麗

本發(fā)明公開了一種求解大規(guī)模多段圖最短路徑的分布式方法，屬于計算機(jī)技術(shù)領(lǐng)域。包括如下步驟：多段圖劃分；各部分子圖求部分最短路徑；各計算節(jié)點通信求多段圖最短路徑。本發(fā)明相較于單機(jī)求解算法，能夠使用分布式系統(tǒng)處理更大規(guī)模的多段圖數(shù)據(jù)；相較于已有的分布式求解算法，滿足負(fù)載均衡的要求并最小化通信開銷。

技術(shù)領(lǐng)域

本發(fā)明屬于計算機(jī)技術(shù)領(lǐng)域，具體涉及一種求解大規(guī)模多段圖最短路徑的分布式方法。

背景技術(shù)

最短路徑問題是圖論中的一個經(jīng)典問題，旨在尋找圖中一對頂點之間的最短路徑。多段圖是一類特殊的加權(quán)有向圖，圖中的頂點分為至少兩個不相交的集合(稱為階段)，其中第一個和最后一個階段有且僅有1個頂點，分別稱為源點和匯點，圖中邊只能從前一階段的頂點指向后一階段的頂點。很多工程應(yīng)用中的實際問題都可以建模為多段圖，所以其應(yīng)用十分廣泛。

隨著多段圖規(guī)模的不斷增大，單機(jī)算法既無法存儲所有的多段圖數(shù)據(jù)，也無法實現(xiàn)最短路徑的求解。此時，分布式算法成為必選。

分布式算法是將圖數(shù)據(jù)盡量均衡地分配到計算機(jī)集群的計算節(jié)點上，然后各個計算節(jié)點并行計算本機(jī)上結(jié)果，再匯總各個部分結(jié)果得到最終結(jié)果。目前，已經(jīng)提出了并行Dijkstra算法、并行Floyd算法、基于ball?string模型的并行算法、Δ-Stepping并行算法等，這些方法雖然也適用于于多段圖，但是沒有充分利用多段圖的特點，通信量過大，計算效率低。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)中存在的上述技術(shù)問題，本發(fā)明提出了一種求解大規(guī)模多段圖最短路徑的分布式方法，設(shè)計合理，克服了現(xiàn)有技術(shù)的不足，具有良好的效果。

為了實現(xiàn)上述目的，本發(fā)明采用如下技術(shù)方案：

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

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

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

(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}是權(quán)重集合，w_i,j,i+1,k是〈v_i,j,v_i+1,k〉的權(quán)重；

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

以表示每個計算節(jié)點能夠存儲的邊的最大數(shù)量；

具體步驟如下：

步驟1：執(zhí)行如下步驟，對多段圖進(jìn)行劃分：

步驟1.1：取當(dāng)前計算節(jié)點編號p＝1，當(dāng)前邊的總數(shù)量Sum＝0，循環(huán)變量i＝1，第p個計算節(jié)點CN_p存儲的第一個階段編號s_p＝i；