基于多鏈路權值減小的動態SPT算法研究

郭文強，肖乾才，李明奇

（1.新疆財經大學 計算機科學與工程學院，新疆 烏魯木齊 830012；2.電子科技大學；四川 成都 611731）

基于多鏈路權值減小的動態SPT算法研究

郭文強1，肖乾才2，李明奇2

（1.新疆財經大學 計算機科學與工程學院，新疆 烏魯木齊 830012；2.電子科技大學；四川 成都 611731）

分支更新的動態最短路徑算法可以有效提高動態最短路徑計算的效率。通過分析動態最短路徑算法研究的現狀和問題，文章對Nfixed（v）的定義進行了改進，解決了原算法中的邊檢查冗余問題，改進了MinD和MaxR算法邊檢查步驟，有效地減少了重復檢查次數。仿真結果顯示，改進后的算法具有更高的效率。

線性規劃；網絡拓撲；路由協議；動態最短路徑算法；動態更新算法

在當今的互聯網中，數據報文由路由器根據轉發表進行轉發。轉發表的構建則由路由協議在網絡拓撲變化同步后更新路由得到。鏈路狀態路由協議通過路由器之間洪泛拓撲信息形成同一拓撲數據庫，之后計算最短路徑樹進而計算路由，然后將路由下發形成轉發表，如OSPF[1]（開放最短路徑優先）以及IS-IS[2]（中間系統對中間系統）協議。

當拓撲變化后，標準的最短路徑算法Dijkstra算法[3]無法判斷改變的拓撲結構對已有SPT的作用范圍。只能全部重新計算。若變化的拓撲較少，實際上變化拓撲對SPT的影響較小，全拓撲計算不僅效率低，而且導致路由不穩定。這種無法判斷變化拓撲對最短路徑樹的影響范圍而只能進行全拓撲計算的最短路徑算法叫作靜態最短路徑算法。……