淺析gis中的網(wǎng)絡分析與最短路徑的實現(xiàn)畢業(yè)論文(編輯修改稿)
2025-07-25 15:48 本頁面
【文章內(nèi)容簡介】 圖 的流程圖。圖 拓撲關(guān)系建立過程流程圖3. 最短路徑算法 由于網(wǎng)絡特征的復雜性和問題的不同特征，最短路徑的算法也表現(xiàn)出多樣性。但總的來說可以按問題的類型、網(wǎng)絡特征和實現(xiàn)的算法進行分類，其中最經(jīng)典，應用最廣泛的的還是 Dijkstra 算法。在實際應用當中，應該根據(jù)不同問題的類型選擇適合于該問題的算法。 算法選擇最短路徑算法選取的原則一般包括：；；定性強。據(jù)統(tǒng)計，目前提出來的最短路徑算法大約有 17 種， 等人對其中的15 種進行了測試，結(jié)果顯示有三種效果比較好，他們分別是 T（graph growth with to queues） 、DKA（the Dijkstra’s algorithm with approximate buckets） 、以及 DKD（the Dijkstra’s implemented with double buckets） 。其中 T 算法的基礎(chǔ)是圖增長理論，較適合于單點到其他各點的最短距離；后兩種算法則都是基于 Dijkstra 的算法，較適合于計算兩點間最短距離 。目前多數(shù)系統(tǒng)解決最短路徑問題采用的是 Dijkstra 算法為理論】【 5基礎(chǔ),只是不同系統(tǒng)對 Dijkstra 算法采用了不同的實現(xiàn)方法。針對不同的網(wǎng)絡特征、應用需求及具體的硬件環(huán)境，各種算法在時間復雜度、空間復雜度、實的難易程度等方面各具特色。 傳統(tǒng) Dijkstra 算法的主要思想Dijkstra 算法的基本思路是：假設每個頂點都有一對標號 ，其中 是從起），（ jjpdjd點 s 到終點 j 的最短路徑長度； 則是從 s 到 j 的最短路徑中 s 的前一點。求解從 s 到jpj 的最短路徑的算法的基本過程如下：初始化。起始點設置為：? ， 為空；? 所有其它點： ∞， =？；?0ds?j ?idip標記起始點 s，計 k=s，其它所有點設為為標記的。檢驗從所有以標記的點 k 到其直接連接的標記點 j 的距離，并設置： ],min[kjjj ldd? 式中， 是從點 k 到 j 的直接連接距離。kjl選取下一個點。從所有為標記的結(jié)點中，選取 中最小的一個 i：jd ]min[dji， 所 有 未 標 記 的 點? 點 i 就被選為最短路徑中的一點，并設為以標記的。找到點 i 的前一點。從以標記的點中找到直接連接到點 i 的點 ，作為前一點，設*j置： *ji?標記點 i。如果所有點以標記，則算法完全退出，否則，記 k=i，轉(zhuǎn)到 2）在繼續(xù)。 經(jīng)典 Dijkstra 算法的實現(xiàn)首先，引進一個輔助向量 D，它的每個分量 D 表示當前所找到的從始點 v 到每個終點 vi 的最短路徑的長度。如 D[3]=2 表示從始點 v 到終點 3 的路徑相對最小長度為2。這里強調(diào)相對就是說在算法過程中 D 的值是在不斷逼近最終結(jié)果但在過程中不一定就等于最短路徑長度。它的初始狀態(tài)為：若從 v 到 vi 有弧，則 D 為弧上的權(quán)值；否則置 D 為∞。顯然，長度為 D[j]=Min{D | vi∈V} 的路徑就是從 v 出發(fā)的長度最短的一條最短路徑。此路徑為(v,vj)。 那么，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是 vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從 v 到 vk 的弧上的權(quán)值，或者是 D[j]和從 vj 到 vk 的弧上的權(quán)值之和。 一般情況下，假設 S 為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（設其終點為 X）或者是弧(v,x) ，或者是中間只經(jīng)過 S 中的頂點而最后到達頂點 X 的路徑。因此，下一條長度次短的最短路徑的長度必是 D[j]=Min{D | vi∈VS} 其中，D 或者是弧(v
數(shù)學相關(guān)推薦
鄂ICP備17016276號-1