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

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

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

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