最短路径演算法.ppt

*;*;背景 最短路徑的求解問題，一般可被分為四類： 單一起點到某一節點(Single-Pair Shortest Path，SPSP) 單一起點到所有節點(Single-Source Shortest-Paths，SSSP) 所有節點到所有節點(All-Pairs Shortest-Paths，APSP) 所有節點到某一終點(Single-Destination Shortest-Paths，SDSP) 對於這問題的解決方法，最廣為人知的是Dijkstra演算法[Dijkstra 1959]，它原本用於解決單一起點到所有節點(SSSP)的問題，由於其時間複雜度和點邊數有密切關係，故不適用於包含大量點邊資訊的圖形。其後的研究除了改良它的資料結構外，在演算過程中靠著輔助資訊減少搜尋範圍的各類方法亦被提出。 ;研究動機與目的 藉由輔助資訊求解最短路徑的方法可依有無分群資訊作為分水嶺。通常有分群資訊的最短路徑演算法，其搜尋時間較為優異，但必需承擔極高的空間負荷。 本研究希望提供一個適用於台灣路網，能在數毫秒內完成搜尋、所需記憶體空間可負荷，且有分群資訊輔助的最短路徑演算法，以供相關應用程式使用。並期望能改善其所需記憶體空間過大的情況，又能保持搜尋速度在一定的水平。 ;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;1b.階層圖記錄資訊之省除 群內圖 起點下一節點(nextNodeinner) findNextNode(s,t)演算法 前提： t = nextNodeborder(s,t) 窮舉s的鄰居節點V，滿足下列條件者即為所求 d1+d2 = distinner(s,t) ;*;2.群間圖之省除 – 只利用群內圖Dijkstra 由於s,t、s,1,t、s,1,2,t的長度相等，依照Dijkstra節點挑選次序的不同，若選中s,t或s,1,t將造成路徑重建過程跨越遺漏邊界點1或2時，路徑無法重建。 但由於邊界點遺漏只發生在同群邊界點間，可以下列方式之一修正 (1) findNextBorderNode演算法中，改用群內圖長度資訊distinner(s,t) 窮舉s所屬群的邊界點bs滿足下列兩條件者即為所求 (1) d1+d2 = distinner(s,t)，且 (2) d1為最小 (2) 改在群內圖中記錄起點下一邊界點nextNodeborder (s,t) ;*;*;*;前處理;*;*;*;*;*;*;*;*;*;*;*;初始參數設定 ;*;1.前處理檔案大小比較 ;1.前處理檔案大小比較 ;1.前處理檔案大小比較 ;2.前處理時間複雜度比較 ;3.最短路徑長度求解時間複雜度比較 ;最短路徑重建時間複雜度整理 ;*;*