[發明專利]一種有權有向動態網絡上的最短路徑估算方法

在審

• 申請號: 201410189825.2
• 申請日: 2014-05-07
• 公開（公告）號: CN103970856A
• 公開（公告）日: 2014-08-06
• 發明（設計）人: 史曉薇;金俊挺;李翠平;陳紅
• 申請（專利權）人: 中國人民大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京紀凱知識產權代理有限公司 11245
• 代理人: 徐寧;孫楠

1.一種有權有向動態網絡上的最短路徑估算方法，其包括以下步驟：

1)以有權有向動態網絡中每一點為樹根節點，構建包括若干正向最短路徑樹和若干反向最短路徑樹的初始樹結構；

2)有權有向動態網絡的結構發生變化時，對有權有向動態網絡中的初始樹結構進行實時更新；

3)根據更新后的樹結構，對有權有向動態網絡中任意兩節點e到f的最短路徑和最短距離進行查詢，找出節點e到節點f的最短路徑。

2.如權利要求1所述的一種有權有向動態網絡上的最短路徑估算方法，其特征在于：所述步驟1)中，構建包括若干正向最短路徑樹和若干反向最短路徑樹的初始樹結構，其構建過程為：

采用MaxDegree最大度方法，在有權有向動態網絡中選取若干點作為landmark葉子節點，以有權有向動態網絡中每一點為樹根節點；

對于每一樹根節點，計算其到所有landmark葉子節點的最短路徑，構成該樹根節點的正向最短路徑樹；

對于每一樹根節點，計算所有landmark葉子節點到該樹根節點的最短路徑，構成該樹根節點的反向最短路徑樹。

3.如權利要求1或2所述的一種有權有向動態網絡上的最短路徑估算方法，其特征在于：所述步驟2)中，對有權有向動態網絡中的初始樹結構進行實時更新，其具體包括以下步驟：

(1)將點的增加和減少以及邊的插入和刪除處理成相應邊權值的變化，相應邊權值的變化和權值改變的邊一起構成權值增加的邊集E+和權值減小的邊集E-；

(2)在有權有向動態網絡中找出權值增加的邊集E+中的邊，將這些邊的權值更改為變化后的權值，并實時更新有權有向動態網絡中的初始樹結構；

(3)在有權有向動態網絡中找出權值減少的邊集E-中的邊，將這些邊的權值更改為變化后的權值，并實時更新有權有向動態網絡中的初始樹結構。

4.如權利要求3所述的一種有權有向動態網絡上的最短路徑估算方法，其特征在于：所述步驟(2)中，采用以下方法實時更新有權有向動態網絡中的初始樹結構，其具體包括以下步驟：

(Ⅰ)采用DASPInc算法對有權有向動態網絡中每一個初始正向最短路徑樹SPT進行實時更新，不同的初始正向最短路徑樹SPT并行更新，其具體包括：

①如果某初始SPT中的任一樹邊對應權值增加的邊集E+中一權值增加的邊，則從該初始SPT上刪除該樹邊；該完整的初始SPT被分解成一棵包含根節點的樹以及一些離散的樹或節點，這些離散的樹和節點構成受影響的節點集N；

②將節點集N中的節點狀態設置為open，初始SPT中不受影響的節點的狀態設置為closed；如果受影響且狀態為open的節點a至少有一個受影響且狀態為closed的父節點p或者至少有一個不受影響的父節點p，則將節點a作為邊界點，將使得根節點到父節點p的距離d(p)與父節點p到節點a的距離w(p,a)之和最小的父節點p作為候選最短路徑父節點，將min(d(p)+w(p,a))作為候選最短距離，并將根節點到節點a的距離d(a)設置為min(d(p)+w(p,a))，該候選最短距離對應的路徑作為候選最短路徑；

③將每個邊界點a、候選最短路徑父節點p和候選最短距離d(a)以形式(a,p,d(a))入鏈表Q；

④對鏈表Q是否為空進行判斷，如果鏈表Q為空，則完成對初始SPT的更新；如果鏈表Q不為空，則從鏈表Q中找出候選最短距離最小的元素，并將該元素以形式(y，x，d(y))出鏈表Q，其具體包括：

首先，將節點y的分支連接于節點y的候選最短路徑父節點x，并將節點y的狀態更改為closed；

其次，對于狀態更改為closed的節點y在有權有向網絡上的每條出邊，其指向的節點q，如果根節點到節點y的距離d(y)與節點y到節點q的距離w(y,q)之和小于根節點到節點q的距離d(q)，即d(y)+w(y,q)<d(q)，則將根節點到節點q的距離d(q)更改為d(y)+w(y,q)，并將(q,y,d(q))入鏈表Q；

⑤重復步驟④，直到鏈表Q為空，完成對初始SPT的更新；

(Ⅱ)采用DASPInc’算法對有權有向動態網絡中每一個初始反向最短路徑樹RSPT進行實時更新，不同初始反向最短路徑樹RSPT并行更新，其具體包括：

①如果某初始RSPT中的任一樹邊對應權值增加的邊集E+中一權值增加的邊，則從該初始RSPT上刪除該樹邊；該完整的初始RSPT被分解成一棵包含根節點的樹以及一些離散的樹或節點，這些離散的樹和節點構成受影響的節點集N’；

②將節點集N’中的節點狀態設置為open，初始RSPT中不受影響的節點的狀態設置為closed；如果受影響且狀態為open的節點a’至少有一個受影響且狀態為closed的子節點p’或者至少有一個不受影響的子節點p’，則將節點a’作為邊界點，將使得子節點p’到根節點的距離d(p’)與節點a’到子節點p’的距離w(a’,p’)之和最小的子節點p’作為候選最短路徑子節點，將min(d(p’)+w(a’,p’))作為候選最短距離，并將節點a’到根節點的距離d(a’)設置為min(d(p’)+w(a’,p’))，將該候選最短距離對應的路徑作為候選最短路徑；

③將每個邊界點a’、候選最短路徑子節點p’和候選最短距離d(a’)以形式(a’,p’,d(a’))入鏈表Q；

④對鏈表Q是否為空進行判斷，如果鏈表Q為空，則完成對初始RSPT的更新；如果鏈表Q不為空，則從鏈表Q中找出候選最短距離最小的元素，并將該元素以形式(y’，x’，d(y’))出鏈表Q，其具體包括：

首先，將節點y’的分支連接于節點y’的候選最短路徑子節點x’，并將節點y’的狀態更改為closed；

其次，對于狀態更改為closed的節點y’在有權有向網絡上的每條入邊，其指出的節點q’，如果節點y’到根節點的距離d(y’)與節點q’到節點y’的距離w(q’,y’)之和小于節點q’到根節點的距離d(q’)，即d(y’)+w(q’,y’)<d(q’)，則將節點q’到根節點的距離d(q’)更改為d(y’)+w(q’,y’)，并將(q’,y’,d(q’))入鏈表Q；

⑤重復步驟④，直到鏈表Q為空，完成對初始RSPT的更新。