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

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

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

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