動態(tài)網絡中最短路徑樹算法的研究.pdf

1、隨著互聯網技術的飛速發(fā)展，人們對信息的傳輸速度要求越來越高，動態(tài)網絡環(huán)境下最短路徑計算問題是近年來研究的熱門內容。在現實生活和實際應用中，最短路徑問題起著非常重要的作用。例如動態(tài)環(huán)境下的最短路徑算法在物流配送、網絡架構和城市規(guī)劃等領域被廣泛的應用。在最短路徑問題的相關研究中，動態(tài)最短路徑樹算法是當前研究的熱點。
　　在以往的最短路徑問題的研究中，都是用靜態(tài)的最短路徑算法計算最短路徑樹，如經典的 Dijkstra算法和 Floyd算

2、法。但靜態(tài)最短路徑算法計算最短路徑樹時存在著明顯的不足。如運用Dijkstra算法計算動態(tài)網絡中的最短路徑樹，當網絡中的鏈路狀態(tài)隨著時間發(fā)生改變時，改變后的最短路徑樹與原來的最短路徑樹并不會發(fā)生太大的變化。由于重新計算整個最短路徑樹，不僅耗費大量的CPU時間，而且因計算的復雜性問題又成為限制網絡的瓶頸。基于上述原因，動態(tài)最短路徑樹算法被提了出來。動態(tài)最短路徑樹算法利用原有的最短路徑樹信息，結合邊權重的變化信息，通過對最短路徑樹中部分受影

3、響節(jié)點最短路徑的更新，來構造新的新的最短路徑樹。
　　本文基于動態(tài)最短路徑樹算法提出一種高效最短路徑樹的維護算法。該算法通過統計分析一定時間內網絡的運行情況，得出權值頻繁變化的邊,對權值頻繁變化的邊給予相應的處理，避免將其加入到最短路徑樹中,從而減少最短路徑樹的更新次數，當網絡中的路由器毀壞或者增加時，通過減少冗余邊的入隊操作,實現路由器在網絡中的增加和刪除，以達到對網絡中的最短路徑樹進行維護。實驗結果表明,與高效的最短路徑樹動態(tài)