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

在審

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

技術領域

本發明涉及一種最短路徑估算方法，特別是關于一種有權有向動態網絡上的最短路徑估算方法。

背景技術

如今，越來越多的應用中需要計算有權有向動態網絡上的最短路徑(SP)。交通路網的權重代表交通擁堵程度，基于當前交通狀況計算出的兩個地點間的最短路徑可以用于導航去目的地的最快路徑。同樣地，如Facebook，Twitter，LinkedIn等社交網絡中，連接兩個用戶的邊的權重代表兩個用戶的親密程度，權重值越小，兩個用戶的聯系越親密，基于用戶間的聯系計算出的兩用戶之間的最短路徑可以幫助一個用戶快速認識另一個用戶，由于動態網絡的規模急劇增加，并且動態網絡中的用戶關系都是有方向且隨時間變化的，因此實時計算出動態網絡中用戶間的最短路徑是非常必要的。

目前，計算最短距離通用的算法是基于三角不等式并利用landmark來估算的，這種算法雖然查詢效率很高，但存在不能返回最短路徑且不能適用于動態圖的缺點。還有一些研究成果提出的基于sketch索引的可處理大規模網絡的算法，雖然可以估算最短距離，也可以得到最短距離對應的最短路徑，但這類算法存在不適用于有權圖的缺點。計算有權圖上最短路徑的通用算法是Dijkstra算法，Dijkstra算法能夠計算得到有權圖上最短路徑的最優解，但當有權圖規模增大時，Dijkstra算法的時間復雜度呈指數級增加，計算效率很低。為克服Dijkstra這類靜態算法的弊端，一些學者研究出可以盡量縮短重新計算最短路徑的動態算法，早期的動態算法只能解決單源點最短路徑問題，后來的動態算法可以計算出任意點對間的近似最短路徑，但每次調用動態算法只能解決一條邊插入、刪除或者一條邊權值增加、減少的問題，這類動態算法的查詢效率雖然相對于Dijkstra算法有所提高，但仍不盡如人意。

發明內容

針對上述問題，本發明的目的是提供一種查詢效率高、擴展性強的有權有向動態網絡上的最短路徑估算方法，該方法針對有權有向動態網絡，能夠一次解決多條邊增刪、權值變化等問題。

為實現上述目的，本發明采取以下技術方案：一種有權有向動態網絡上的最短路徑估算方法，其包括以下步驟：1)以有權有向動態網絡中每一點為樹根節點，構建包括若干正向最短路徑樹和若干反向最短路徑樹的初始樹結構；2)有權有向動態網絡的結構發生變化時，對有權有向動態網絡中的初始樹結構進行實時更新；3)根據更新后的樹結構，對有權有向動態網絡中任意兩節點e到f的最短路徑和最短距離進行查詢，找出節點e到節點f的最短路徑。

所述步驟1)中，構建包括若干正向最短路徑樹和若干反向最短路徑樹的初始樹結構，其構建過程為：采用MaxDegree最大度方法，在有權有向動態網絡中選取若干點作為landmark葉子節點，以有權有向動態網絡中每一點為樹根節點；對于每一樹根節點，計算其到所有landmark葉子節點的最短路徑，構成該樹根節點的正向最短路徑樹；對于每一樹根節點，計算所有landmark葉子節點到該樹根節點的最短路徑，構成該樹根節點的反向最短路徑樹。

所述步驟2)中，對有權有向動態網絡中的初始樹結構進行實時更新，其具體包括以下步驟：(1)將點的增加和減少以及邊的插入和刪除處理成相應邊權值的變化，相應邊權值的變化和權值改變的邊一起構成權值增加的邊集E+和權值減小的邊集E-；(2)在有權有向動態網絡中找出權值增加的邊集E+中的邊，將這些邊的權值更改為變化后的權值，并實時更新有權有向動態網絡中的初始樹結構；(3)在有權有向動態網絡中找出權值減少的邊集E-中的邊，將這些邊的權值更改為變化后的權值，并實時更新有權有向動態網絡中的初始樹結構。