[發明專利]用于多路徑路由的多條部分不相交最短路徑快速尋找方法

有效

• 申請號: 201810841121.7
• 申請日: 2018-07-27
• 公開（公告）號: CN108924053B
• 公開（公告）日: 2021-01-29
• 發明（設計）人: 郭龍坤;鄧蕓蕓;黃培煌;郝震東;陳建利;楊旸
• 申請（專利權）人: 福州大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/735;H04L12/24
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.一種用于多路徑路由的多條部分不相交最短路徑快速尋找方法，其特征在于，按照如下步驟實現：

步驟S1：將有向網絡表示為有向圖模型G＝(V,E)；

步驟S2：從所述有向圖模型G中獲取一條最短s-t路徑P^*，并令Ω＝{P^*}，Ω表示有向圖模型G中最短s-t路徑的集合；

步驟S3：根據Ω中的所有路徑，建立對應所述有向圖G的一個傳統余圖

步驟S4：基于所述傳統余圖構造點分解余圖

步驟S5：從所述點分解余圖中獲取一條最短s-t路徑Q^*，沿此路徑Q^*對路徑P^*進行增廣；

步驟S6：分解獲取螺旋最優路徑；

步驟S7：判斷所有最短s-t路徑P^*是否處理完，若是，則結束，并輸出多條部分不相交最短路徑；否則返回所述步驟S3；

在所述步驟S1中，

將所述有向網絡表示為所述有向圖模型G＝(V,E)，其中，V為有向圖中的頂點，E為有向圖中的邊，n＝|V|為有向圖G中頂點的個數，m＝|E|為有向圖G中邊的條數，源點為s，目的節點為t，權重函數為w(e)，共享點數目的花費函數為c(e)，共享點數目的上界為δ，P(u,v)為從節點u到節點v的一條路徑；

尋找部分不相交最短路徑方法的目標是得到一組路徑，使得路徑的總權重最小，并且滿足下列3個約束條件：1)除源點和目的節點外，圖中每個節點的出度等于入度；2)所有路徑的共享點至多δ個；3)0-1變量：若邊包含在所求路徑內，則取1；反之，取0；即優化以下數學模型：

x_e∈{0,1} e∈E

其中，x_e表示集合{0,1}的非空真子集，w(e)表示邊e的權重，k表示不相交路徑的條數，s表示最短路徑P^*的起點，t表示最短路徑P^*的終點，δ⁺(v)表示離開點v的邊集，δ^-(v)表示進入點v的邊集，c(e)邊e的花費，表示點分解余圖；

在所述步驟S3中，所述傳統余圖其中，是由P^*的反向邊組成的路徑，并且權重的值為原邊的相反數，對每條邊e＝(u,v)∈P^*，將e'＝(v,u)加入并且權重為w(e')＝-w(e)；

在所述步驟S4中，還包括如下步驟：

步驟S41：把路徑P^*上每個內部的點v，除源點s和目的節點t以外，分解成點v₁和v₂；

步驟S42：在所述分解余圖中加入兩種類型的邊：權重為0、花費為1的邊e(v₁,v₂)和權重為0、花費為0的邊e(v₂,v₁)；

步驟S43：替換原圖邊中至少有一個點在的邊：

1)若則替換為e(v₁,u₂)；

2)若且則替換為e(x,u₁)；

3)若且則替換為e(v₂,y)；

同時，所有替換后的邊的權重等于原邊的權重，花費均為0。

2.根據權利要求1所述的用于多路徑路由的多條部分不相交最短路徑快速尋找方法，其特征在于，在所述步驟S2中，從所述有向圖模型G中通過迪杰斯特拉方法獲取一條最短s-t路徑P^*。

3.根據權利要求1所述的用于多路徑路由的多條部分不相交最短路徑快速尋找方法，其特征在于，在所述步驟S5中，從所述分解余圖中通過使用迪杰斯特拉方法獲取一條最短s-t路徑，也即從所述分解余圖中獲取一條花費不大于δ的最短s-t路徑，將上述問題記為BRSP問題，通過運用動態規劃的方法在O(δ|E|)的時間內得到BRSP問題的最優解，即一條花費不大于δ的最短s-t路徑Q，同時獲取下一條最短s-t路徑，令P^*的下標i＝i+1與Ω＝{P₁^*,...,P_i^*}。

4.根據權利要求1所述的用于多路徑路由的多條部分不相交最短路徑快速尋找方法，其特征在于，在所述步驟S6中，記P^*∪Q為最優解，表示路徑P^*和路徑Q中的所有邊去掉相同頂點之間但方向相反的邊對的集合；把P^*∪Q分解成P₁和P₂兩條路徑，獲取螺旋最優路徑。