【導(dǎo)讀】最短路徑分析是GIS地理網(wǎng)絡(luò)分析功能中的一個關(guān)鍵問題。最短路徑的經(jīng)典算法，是許多工程解決最短路徑問題的理論基礎(chǔ)。響了算法的速度。本文在對傳統(tǒng)Dijkstra算法分析的基礎(chǔ)上，對其進行了優(yōu)化，優(yōu)?；惴ㄖ粚ψ疃搪窂缴瞎?jié)點的鄰居做了處理，而不涉及到其他節(jié)點。化算法中計算的節(jié)點數(shù)大幅減少，提高了算法的速度。本文通過實驗和實際應(yīng)用

　　

【正文】 率，在道路節(jié)點路段數(shù)量多的空間拓?fù)浣Y(jié)構(gòu)中尤為適用。 26 第 5章 總結(jié)與展望 全文總結(jié) 本文基于 Dijkstra算法，針對 Dijkstra算法在實際應(yīng)用中 搜索速度慢，搜索效率低，時間花費多 的的缺陷，對其進行了優(yōu)化。優(yōu) 化算法只對最短路徑上節(jié)點的鄰居做處理，而不涉及到其他節(jié)點，每個搜索過程不必全部遍歷或者較少地遍歷臨時標(biāo)記點，既縮小了搜索范圍，又保證了遍歷搜索 100%的搜索成功率，從而提高了搜索效率，節(jié)省了時間， 適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，性能穩(wěn)定 。 展望 目前基于 Dijkstra 算法的優(yōu)化算法很多，但是這些優(yōu)化算法大多只對它進行了單方面的優(yōu)化。實際上，在一個網(wǎng)絡(luò)中，盡管節(jié)點和邊很多，但與網(wǎng)絡(luò)中某一節(jié)點相關(guān)的邊和節(jié)點卻是有限的。以鄰接矩陣或關(guān)聯(lián)矩陣為基礎(chǔ)的算法，有大量的 0元素或 ∞元素，這些無效元素占用了大量的計算機內(nèi)存，所以需在此 基礎(chǔ)上進行數(shù)據(jù)存儲的優(yōu)化，如果在記錄網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系時，只記錄與網(wǎng)絡(luò)節(jié)點相關(guān)的節(jié)點和邊，則可以大大減少矩陣的行或列名這樣一來構(gòu)成的點 邊關(guān)系矩陣也大大減少了0 元素或 ∞元素，從而起到節(jié)約內(nèi)存。 27 參考文獻 [1] 羅理，王鋒 .基于 Dijkstra 的最短路徑改進算法 [N].湖北汽車工業(yè)學(xué)院學(xué)報 . 2020 年 6月 ,第 21卷第 2 期 . [2] 徐寅峰，劉明，蘇兵 .不完全信息下交通網(wǎng)絡(luò)最短路徑的求解方法 [J].中國科技論文在線 . [3] 焦學(xué)軍，秦奮，王海鷹 . A 星算法在城鎮(zhèn)地價評估中的應(yīng)用 [J]. 科苑論談． [4] 張寧 .遺傳算法的特點及其應(yīng)用 [Z]. [5] 李擎，謝四江，童新海，王志良 . 一種用于車輛最短路徑規(guī)劃的自適應(yīng)遺傳算法機器與 Dijkstra 和 A*算法的比較 [N].北京科技大學(xué)學(xué)報 .2020 年 11 月，第 28卷第 11 期 . [6] 董鑫，鄭逢斌，李莘莘 . Dijkstra 算法的改進及其在警用 GIS中的實現(xiàn) [N]. 鄭州輕工業(yè)學(xué)院學(xué)報 (自然科學(xué)版 ). 2020 年 lO 月，第 22 卷第 5 期 . [7] 章永龍 .Dijkstra 最短路徑算法優(yōu)化 [N]. 南昌工程學(xué)院學(xué)報 , 2020 年 8 月 ,第 25 卷第 3 期 . [8] 陳尹軍，王翠玲 .基于 Dijkstra 算法的公路網(wǎng)最短路徑查詢實現(xiàn) [J]. 中國科技論文在線 . [9] 夏華麗，寧書年 .Dijkstra 算法在物流配送運輸規(guī)劃中的最短路徑研究 [J].中國科技論文在線 . [10] 古凌嵐 .GIS 最短路徑分析中 Dijkstra 算法的優(yōu)化 [J].計算機與數(shù)字工程 .2020，第 34 卷第 12期 . [11] 馮桂蓮 .基于 Dijkstra 算法的最短路徑的實現(xiàn) [N].青海大學(xué)學(xué)報 (自然科學(xué)版 ).2020 年 2月，第 25卷第 1期 . [12] 陳益富，盧 瀟，丁豪杰 . 對 Dijkstra 算法的優(yōu)化策略研究 [N]. 計算機技術(shù)與發(fā)展 . 2020, 第 l6 卷第 9期 . [13] 王 濤 ,李偉生 .最短路徑子圖 [N].北方 交通大學(xué)學(xué)報 .2020 年 ,第 28 卷第 2 期 . 28 [14] 李玲，劉正綱，張強 . 基于 Mapx 的最短路徑選擇算法的實現(xiàn) [J]. 中國科技論文在線 . [15] 曹陽 . 數(shù)據(jù)結(jié)構(gòu)中最短路徑算法的實現(xiàn) [N]. 宜賓學(xué)院學(xué)報 .2020，第 6 期 . 29 附 錄 有向邊類， class Edge//抽象邊類，用于描述道路 using System。 using 。 using 。 namespace WindowsApplication1 { /// summary /// 有向邊類 /// /summary class Edge //抽象邊類 { private string s_StartNodeID=N/A。 //起點ＩＤ private string s_EndNodeID = N/A。 //終點ＩＤ private double s_Weight=1。 //權(quán)值，代價 public string StartNodeID { get { return 。 } set { = value。 } } public string EndNodeID { get { return 。 } set { = value。 } } public double Weight { get { return 。 } set { = value。 30 } } } } 節(jié)點類， class Node//抽象節(jié)點類，用于描述具體地點 using System。 using 。 using 。 using 。 namespace WindowsApplication1 { /// summary /// 節(jié)點類 /// /summary class Node //節(jié)點則抽象成 Node類，一個節(jié)點上掛著以此節(jié) 點作為起點的 ―出邊 ‖ { private string iD 。 private ArrayList edgeList 。//Edge的集合－－出邊表 public Node(string id ) { = id 。 = new ArrayList() 。 } public string ID { get { return 。 } } public ArrayList EdgeList { get { return 。 } set { edgeList = value。 } } } } 計算最小路徑， RoutePlanResult 方法，用于獲取權(quán)值最小的路徑 using System。 using 。 using 。 31 using 。 namespace WindowsApplication1 { class RoutePlanner { public RoutePlanner() { } region Paln //獲取權(quán)值最小的路徑 public RoutePlanResult Paln(ArrayList nodeList, string originID, string destID) { PlanCourse planCourse = new PlanCourse(nodeList, originID)。 Node curNode = (planCourse, nodeList, originID)。 region 計算過程 while (curNode != null) { PassedPath curPath = planCourse[]。//從ＨＡＳＨ中取回ＮＯＤＥＩＤ節(jié)點的 PassedPath foreach (Edge edge in ) { if ( != originID) //過濾掉源節(jié)點 { PassedPath targetPath = planCourse[]。 double tempWeight = + 。 if (tempWeight ) { = tempWeight。 ()。 for (int i = 0。 i 。 i++) { ([i].ToString()) 。 } ()。 } } } //標(biāo)志為已處理 planCourse[].BeProcessed = true。 //獲取下一個未處理節(jié)點 curNode = (planCourse, nodeList, originID)。 } endregion //表示規(guī)劃結(jié)束 return (planCourse, destID)。 } 32 endregion region private method region GetResult //從 PlanCourse表中取出目標(biāo)節(jié)點的 PassedPath，這個 PassedPath即是規(guī)劃結(jié)果 private RoutePlanResult GetResult(PlanCourse planCourse, string destID) { PassedPath pPath = planCourse[destID]。 if ( == ) { RoutePlanResult result1 = new RoutePlanResult(null, )。 return result1。 } string[] passedNodeIDs = new string[]。 for (int i = 0。 i 。 i++) { passedNodeIDs[i] = [i].ToString()。 } RoutePlanResult result = new RoutePlanResult(pa