【導讀】隨著計算機和地理信息科學的發(fā)展，GIS的應用領域越來越廣。算法之一就是Dijkstra算法，許多工程中解決最短路徑問題都是采用這種算法。傳統(tǒng)的Dijkstra算法在求解節(jié)點間最短路徑時，對已標識節(jié)點外的大量節(jié)點進行了計算，從而影響了算法的速度。本文在傳統(tǒng)Dijkstra算法的基礎上，對其進行了優(yōu)化，此優(yōu)化。實際應用對改進后的算法進行了簡單的驗證。

　　

【正文】 中 Dijkstra 算法的優(yōu)化 [J].計算機與數字工程 ,2020,34(12):37. [11] 馮桂蓮 .基于 Dijkstra 算法的最短路徑的實現 [N].青海大學學報 (自然科學版 ),2020(3). [12] 陳益富 ,盧瀟 ,丁豪杰 .對 Dijkstra 算法的優(yōu)化策略研究 [J].計算機技術與發(fā)展 , 2020,12(3):109112. [13] 王濤 ,李偉生 .最短路徑子圖 [N].北方交通大學學報 ,2020(2). [14] 李玲 ,劉正綱 ,張強 .基于 Mapx 的最短路徑選擇算法的實現 [J].中國科技論文在線 ,2020,3(2):1115. [15] CaoYang. Data structure the realization of the shortest path algorithm [J]. 2020,5(9):1221. [16] IEEE Standard VHDL Language Reference Manual IEEE Press ,1987:2839. 26 附錄一 有向邊類， 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。 //權值，代價 public string StartNodeID { get { return 。 } set { = value。 } } public string EndNodeID { get { return 。 } set { = value。 } } 27 public double Weight { get { return 。 } set { = value。 } } } } 節(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 。 } } 28 public ArrayList EdgeList { get { return 。 } set { edgeList = value。 } } } } 計算最小路徑， RoutePlanResult 方法，用于獲取權值最小的路徑 using System。 using 。 using 。 using 。 namespace WindowsApplication1 { class RoutePlanner { public RoutePlanner() { } region Paln //獲取權值最小的路徑 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 ) { 29 if ( != originID) //過濾掉源節(jié)點 { PassedPath targetPath = planCourse[]。 double tempWeight = + 。 if (tempWeight ) { = tempWeight。 ()。 for (int i = 0。 i 。 i++) { ([i].ToString()) 。 } ()。 } } } //標志為已處理 planCourse[].BeProcessed = true。 //獲取下一個未處理節(jié)點 curNode = (planCourse, nodeList, originID)。 } endregion //表示規(guī)劃結束 return (planCourse, destID)。 } endregion region private method region GetResult //從 PlanCourse表中取出目標節(jié)點的 PassedPath，這個 PassedPath即是規(guī)劃結果 private RoutePlanResult GetResult(PlanCourse planCourse, string destID) { PassedPath pPath = planCourse[destID]。 if ( == ) { RoutePlanResult result1 = new RoutePlanResult(null, )。 return result1。 30 } string[] passedNodeIDs = new string[]。 for (int i = 0。 i 。 i++) { passedNodeIDs[i] = [i].ToString()。 } RoutePlanResult result = new RoutePlanResult(passedNodeIDs, )。 return result。 } endregion region GetMinWeightRudeNode //從 PlanCourse取出一個當前累積權值最小，并且沒有被處理過的節(jié)點 private Node GetMinWeightRudeNode(PlanCourse planCourse, ArrayList nodeList, string originID) { double weight = 。 Node destNode = null。 foreach (Node node in nodeList) { if ( == originID) { continue。 } PassedPath pPath = planCourse[]。 if () { continue。 } if ( weight) { weight = 。 destNode = node。 } } return destNode。 } 31 endregion endregion } 按鈕事件，從 sqlserver2020 數據庫節(jié)點表中獲取節(jié)點，載入到應用程序中 private void button1_Click(object sender, EventArgs e) { Net my = new Net()。 //產生節(jié)點，從數據庫取得 NativeNet mynative = new NativeNet()。 DataSet resultsnode