[發明專利]一種分布式計算有向圖圍長的方法

有效

• 申請號: 201711237056.9
• 申請日: 2017-11-30
• 公開（公告）號: CN108154530B
• 公開（公告）日: 2020-07-10
• 發明（設計）人: 華強勝;金海;錢立祥
• 申請（專利權）人: 華中科技大學
• 主分類號: G06T7/62
• 分類號: G06T7/62
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

1.一種分布式計算有向圖圍長的方法，其特征在于，所述方法包括：

S1，將有向圖G中所有權值為負的邊轉化為非負；

S2，圖G中每一個點執行有距離限制參數t的Bounded BFS算法；

S3，根據Bounded BFS算法的結束條件，更新有向圖圍長g的下界α或上界β；

S4，根據β、α和Bounded BFS的結束條件，刪除圖G中權值之和大于α或β的路徑；所述步驟S4包括：

S4.1，根據下界α和Bounded BFS的結束條件，刪除圖中權值之和大于α的路徑；

S4.2，根據上界β和Bounded BFS的結束條件，刪除圖中權值之和大于β的路徑；

S5，通過α和β更新距離限制參數t；

S6、重復執行步驟S2-S5直到β-α≤1成立，得到圖G的圍長g＝β。

2.根據權利要求1所述的一種分布式計算有向圖圍長的方法，其特征在于，所述步驟S1包括：

S1.1，計算有向圖G的最小平均值環λ；

S1.2，將圖G中邊的權值更新w`_ij＝w_ij-λ，其中，w_ij表示邊(i,j)的權值；

S1.3，再計算圖G中結點i和結點j到點1的距離，記為P(i)和P(j)；

S1.4，再次更新圖G中邊的權值

3.根據權利要求1所述的一種分布式計算有向圖圍長的方法，其特征在于，所述步驟S2包括：

S2.1，設置Bounded BFS的結束條件，具體為：

結束條件1，有向圖中某一個點被Bounded BFS訪問兩次；

結束條件2，從有向圖中某一點s開始的Bounded BFS再一次訪問點s；

結束條件3，圖G中所有的點都無法再進一步執行Bounded BFS；

S2.2，有向圖G中每個點執行距離限制參數為t的寬度優先算法，即為Bounded BFS。

4.根據權利要求3所述的一種分布式計算有向圖圍長的方法，其特征在于，所述步驟S3包括：

S3.1，若觸發Bounded BFS的結束條件1，點v被Bounded BFS訪問兩次，則v等待n輪后計算最短路徑d[s,v]，其中，s為Bounded BFS的起始點；

S3.2，更新下界α＝max{d[s,v]:s,v∈G}，結束步驟S3；

S3.3，若觸發Bounded BFS的結束條件2或3，則更新上界β＝t。

5.根據權利要求4所述的一種分布式計算有向圖圍長的方法，其特征在于，所述步驟S4.1包括：

S4.1.1，對于有向圖G中每個被Bounded BFS訪問兩次的結點v，發送消息給它的前驅結點u，若α＜d[s,u]，則進入步驟S4.1.2；

S4.1.2，對于每一個從點v接收到消息的結點u，刪除邊(u,v)，然后點u發送消息給它的每一個前驅結點；

S4.1.3，當Bounded BFS的起始點s接收到消息時，s停止發送消息；當圖中不再有消息傳遞時，步驟S4.1停止。

6.根據權利要求4所述一種分布式計算有向圖圍長的方法，其特征在于，步驟S4.2包括以下步驟：

S4.2.1，對于有向圖G中每個被以點s為起始點的Bounded BFS再次訪問的起始點s，發送消息給它的前驅結點u，若β＜d[s,u]，則進入步驟S4.2.2；

S4.2.2，對于每一個從v點接收到消息的結點u，刪除邊(u,v)，然后u發送消息給它的每一個前驅結點；

S4.2.3，當Bounded BFS的起始點s再次接收到消息時，s停止發送消息；當圖中不再有消息傳遞時，步驟S4.2停止。

7.根據權利要求1所述的一種分布式計算有向圖圍長的方法，其特性在于，步驟S5包括以下步驟：

S5.1，判斷β-α≤1是否成立，若成立，則設置g＝β并結束算法；否則，進入步驟S5.2；

S5.2，更新距離限制參數并向圖G中廣播新的距離限制參數t，返回步驟S2。