本文關(guān)鍵詞：網(wǎng)絡(luò)最短路徑問題的研究與應(yīng)用

  更多相關(guān)文章： 最短路徑 Bellman-Ford算法 Floyd算法 改進算法 隨機網(wǎng)絡(luò)

【摘要】：最短路徑問題是圖論和網(wǎng)絡(luò)優(yōu)化理論研究的主要問題,用于求解網(wǎng)絡(luò)中任意兩點之間的最短路徑。隨著科技的發(fā)展,最短路徑問題在計算機科學、地理信息科學、通信與軍事運籌學等領(lǐng)域發(fā)揮越來越大的作用。因此,研究最短路徑問題意義重大。首先,通過分析Bellman-Ford算法,針對其求解最短路長重復計算量大,尋找最短路徑繁瑣的問題,本文提出Ford算法的改進算法。改進算法通過引入路權(quán)數(shù)組有效降低了算法的時間復雜度,同時借助前點標號數(shù)組增強了尋路直觀性。編寫MATLAB程序,并在大型隨機網(wǎng)絡(luò)中仿真實驗,結(jié)果顯示Ford算法的改進算法更為有效。其次,對Floyd算法進行深入研究,通過引進迭代矩陣和下標標注法對其進行改進。Floyd改進算法提高了計算最短路長的效率,簡化了尋找最短路徑的步驟。給出算法復雜度、可行性分析和具體實例,并用Floyd改進算法與原算法計算大型網(wǎng)絡(luò)最短路,理論分析和仿真結(jié)果都說明了改進算法的準確性和高效性。再次,本文提出用三個值標記一個節(jié)點的拓撲排序法的修正算法,修正算法通過增加前點標號改善了拓撲排序法求解最短路徑繁瑣的問題,通過只更新與出弧相連節(jié)點的標記,簡化了計算量,提高了計算效率。最后,簡單介紹最短路徑問題在通信中的應(yīng)用及其推廣應(yīng)用。
【學位授予單位】：南京郵電大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 徐翠霞;;無環(huán)網(wǎng)絡(luò)中的最短路徑問題研究[J];科技廣場;2007年03期

2 校景中;肖麗;;最短路徑問題的優(yōu)化算法研究[J];西南民族大學學報(自然科學版);2012年03期

3 張森;;改進蟻群算法求解最短路徑問題[J];電子世界;2013年16期

4 張濤;陳忠;呂一兵;;求解最短路徑問題的一種改進的人工蜂群算法[J];青海師范大學學報(自然科學版);2013年01期

5 余金山;;最短路徑問題的解答圖算法[J];華僑大學學報;1984年02期

6 柴登峰,張登榮;前N條最短路徑問題的算法及應(yīng)用[J];浙江大學學報(工學版);2002年05期

7 畢亞軍;王曉威;鄧鳳茹;;網(wǎng)絡(luò)圖任意兩點間最短路徑問題的計算機實現(xiàn)[J];科技資訊;2006年31期

8 馮震;劉佳;李靖;曹延飛;;復雜網(wǎng)絡(luò)中最短路徑問題的求解算法研究[J];自動化技術(shù)與應(yīng)用;2010年03期

9 伍建華,祁文青,晏伯武;單匯最短路徑問題的一種算法[J];黃石高等�？茖W校學報;2001年02期

10 莫忠息;;網(wǎng)絡(luò)中含有負圈的最短路徑問題[J];武漢大學學報(自然科學版);1993年05期

中國重要會議論文全文數(shù)據(jù)庫 前4條

1 崔嵐;阮秋琦;;結(jié)點有擁塞的動態(tài)最短路徑問題的算法研究[A];第十二屆全國信號處理學術(shù)年會（CCSP-2005）論文集[C];2005年

2 劉翔;袁俊江;;改進遺傳算法在不確定性最短路徑問題的應(yīng)用[A];第六屆中國不確定系統(tǒng)年會論文集[C];2008年

3 王海梅;周獻中;;直線優(yōu)化A*算法在最短路徑問題中的高效實現(xiàn)[A];全國第19屆計算機技術(shù)與應(yīng)用（CACIS）學術(shù)會議論文集（下冊）[C];2008年

4 易正俊;黃華;張業(yè)亭;;模糊最短路徑問題及標號法的實現(xiàn)[A];第五屆中國不確定系統(tǒng)年會論文集[C];2007年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 于剛;走最近的路還是走最快的路？[N];中國國防報;2006年

中國博士學位論文全文數(shù)據(jù)庫 前3條

1 俞峰;復雜動態(tài)隨機網(wǎng)絡(luò)最短路徑問題研究[D];浙江大學;2009年

2 張鐘;大規(guī)模圖上的最短路徑問題研究[D];中國科學技術(shù)大學;2014年

3 李杰;鄰域可視性相關(guān)的路徑規(guī)劃問題研究[D];中國科學技術(shù)大學;2011年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 蔣騰飛;網(wǎng)絡(luò)最短路徑問題與應(yīng)用研究[D];南京郵電大學;2013年

2 朱學智;基于遺傳算法的最短路徑問題研究[D];中國科學技術(shù)大學;2015年

3 梁娟;網(wǎng)絡(luò)最短路徑問題的研究與應(yīng)用[D];南京郵電大學;2015年

4 邱釗;K最短路徑算法及其應(yīng)用研究[D];電子科技大學;2014年

5 劉佳;復雜網(wǎng)絡(luò)中最短路徑問題的優(yōu)化算法研究[D];太原科技大學;2007年

6 王東旭;基于KEGG的代謝通路最短路徑問題的研究[D];哈爾濱工業(yè)大學;2007年

7 吳虎發(fā);蟻群優(yōu)化算法在求解最短路徑問題中的研究與應(yīng)用[D];安徽大學;2012年

8 崔樹林;求解不確定馬爾克夫決策問題[D];吉林大學;2006年

9 方志斌;蟻群算法及其在路徑優(yōu)化問題中的研究[D];東華理工大學;2012年

10 平曉慧;最短路徑問題的并行算法研究[D];大連理工大學;2006年

，

本文編號：1164133