求圖中受限制的所有最短路徑算法的分析與研究.pdf

1、最短路徑算法是圖論、計算機網(wǎng)絡、地理信息系統(tǒng)、交通咨詢等諸多領域中研究的熱門課題。它主要應用于路徑搜索、網(wǎng)絡尋優(yōu)等方面。最短路徑算法中較經(jīng)典的有Dijkstra、Floyd等算法,這些算法只涉及到單目標優(yōu)化,即只求出一條從一個頂點到另外一個頂點的最短路徑及長度。隨著科學技術的發(fā)展,單一目標往往很難準確地描述和解決現(xiàn)實生活中的問題,因此,帶限制條件的最短路徑算法具有較強的實用價值和更廣泛的應用領域。本文就是基于此背景,展開對受限制的最短路

2、徑算法的討論和研究的。本文提出了受限制條件的最短路徑算法。這些算法在物流運輸、交通路線的確定上起著重要的作用。本文首先介紹了最短路徑算法的研究現(xiàn)狀、研究意義。其次介紹了圖以及常用算法的相關知識。接著對受限制最短路徑算法以及本文提出的算法進行了詳細地闡述。
　　本文重點在于第三章。一共提出了三種相關算法。1、提出了一個求圖中一個頂點到另外一個頂點間所有最短路徑的算法。該算法是從終點開始對鄰接到該點的結點出度減1,求出終點到該結點的當

3、前最短路徑長度,保存其有效直接后繼結點,對出度為0的結點做同樣的操作,依次類推,直到出度為0的結點都被處理完時,可以求出源點到終點的最短路徑長度以及最短路徑上各個結點的有效直接后繼結點序列。本算法較以前的同類算法有易于理解,時間復雜度低等優(yōu)點,其時間復雜度為O(n~2×(sh1(G,i,j))(n為圖中結點總數(shù),sh1(G,i,j)為圖中實際的最短路徑條數(shù))。2、提出了一個受費用和頂點數(shù)限制的最短路徑算法,該算法為每個結點各設置了一個狀

4、態(tài)鏈表,從源點狀態(tài)開始求出其鄰接點的滿足限制條件的狀態(tài),并將狀態(tài)存放在該結點的狀態(tài)鏈表中,依此類推,直到終點為止。此時,終點的狀態(tài)鏈表中存放的是滿足限制條件的狀態(tài),路徑長度最小的一個或者多個狀態(tài)是滿足限制條件的最短路徑的終點狀態(tài),也可以求出滿足限制條件的次短和再次短路徑。其時間復雜度為O(n~2×N)(n為圖中頂點個數(shù),N為結點的狀態(tài)數(shù)目的最大值)。3、提出了一個改進的受費用和頂點數(shù)限制的最短路徑算法。該算法利用頂點數(shù)限制為樹高,費用限