1、Dijkstra 最短路徑算法的一種高效率實現*關鍵詞最短路徑算法；網絡分析；地理信息系統分類號P208；O22 An Efficient Implementation of Shortest Path AlgorithmBased on Dijkstra Algorithm Yue YangGong Jianya(National Laboratory for Information Engineering in Surveying, Mapping and Remote Sensing，WTUSM, 129 Luoyu Road, Wuhan, China, 430079) Abstrac

2、tWith the development of geographic information science and the wide use of GIS software, more and more needs are required to the network analyses. As the key of network analyses, computing the shortest paths over a network is an important problem that scholars facus on. Start with the data structur

3、e during its computation process and combined with F.Benjamin Zhans evaluation of a set of 15 shortest path algorithms, this paper presents an efficient method of realize the shortest path algorithm which is based on Dijkstra algorithm. Result shows that this method performs well in practice.Key wor

4、dsshortest path algorithm； network analysis； GIS 隨著計算機的普及以及地理信息科學的發展，GIS因其強大的功能得到日益廣泛和深入的應用。網絡分析作為GIS最主要的功能之一，在電子導航、交通旅游、城市規劃以及電力、通訊等各種管網、管線的布局設計中發揮了重要的作用，而網絡分析中最基本最關鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量等。相應地，最短路徑問題就成為最快路徑問題、最低費用問題等。由于最短路徑問題在實際中常用于汽車導航系統以及各種應急系統等（如110報警、119火警以及醫療救

5、護系統），這些系統一般要求計算出到出事地點的最佳路線的時間應該在1 s3 s內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現應該是高效率的。其實,無論是距離最短、時間最快還是費用最低，它們的核心算法都是最短路徑算法。經典的最短路徑算法Dijkstra算法是目前多數系統解決最短路徑問題采用的理論基礎，只是不同系統對Dijkstra算法采用了不同的實現方法。據統計，目前提出的此類最短路徑的算法大約有17種。F.Benjamin Zhan等人對其中的15種進行了測試，結果顯示有3種效果比較好，它們分別是：TQQ（graph growth with two queues

6、）、DKA (the Dijkstras algorithm implemented with approximate buckets) 以及 DKD (the Dijkstras algorithm implemented with double buckets )，這些算法的具體內容可以參見文獻1。其中TQQ算法的基礎是圖增長理論，較適合于計算單源點到其他所有點間的最短距離；后兩種算法則是基于Dijkstra的算法，更適合于計算兩點間的最短路徑問題1。總體來說，這些算法采用的數據結構及其實現方法由于受到當時計算機硬件發展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當的時間效率

7、來換取空間節省。目前，空間存儲問題已不是要考慮的主要問題，因此有必要對已有的算法重新進行考慮并進行改進，可以用空間換時間來提高最短路徑算法的效率。 1經典Dijkstra算法的主要思想Dijkstra算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等于零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：1) 初始化。起源點設置為： ds=0, ps為空; 所有其他點: di=, pi=?; 標記起源點s，記k=s,其他所有點設為未標記的。2

8、) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置： dj=mindj, dk+lkj 式中，lkj是從點k到j的直接連接距離。3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i： di=mindj, 所有未標記的點j 點i就被選為最短路徑中的一點，并設為已標記的。4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置： i=j* 5) 標記點i。如果所有點已標記，則算法完全推出，否則，記k=i，轉到2) 再繼續。 2已有的Dijkstra算法的實現從上面可以看出，在按標記法實現Dijkstra算法的過程中，核心步驟就是從未標記的點中

9、選擇一個權值最小的弧段，即上面所述算法的2)5)步。這是一個循環比較的過程，如果不采用任何技巧，未標記點將以無序的形式存放在一個鏈表或數組中。那么要選擇一個權值最小的弧段就必須把所有的點都掃描一遍，在大數據量的情況下，這無疑是一個制約計算速度的瓶頸。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊的權值進行順序排列，這樣每循環一次即可取到符合條件的點，可大大提高算法的執行效率。另外，GIS中的數據 (如道路、管網、線路等)要進行最短路徑的計算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在GIS中稱為構建網絡的拓撲關系 (由于這里的計算與面無關，所以拓撲關系中只記錄了線與結點的關

10、系而無線與面的關系，是不完備的拓撲關系)。如果用一個矩陣來表示這個網絡，不但所需空間巨大，而且效率會很低。下面主要就如何用一個簡潔高效的結構表示網的拓撲關系以及快速搜索技術的實現進行討論。網絡在數學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表4 表示，其優缺點的比較見表 1。 表 1幾種圖的存儲結構的比較 Tab. 1The Comparsion of Several Graph for Storing Structures名稱 實現方法 優點 缺點 時間復雜度鄰接矩陣 二維數組 1. 易判斷兩點間的關系

11、 占用空間大 O(n2+m*n) 2. 容易求得頂點的度 鄰接表 鏈表 1. 節省空間 1. 不易判斷兩點間的關系 O(n+m)或O(n*m) 2. 易得到頂點的出度 2. 不易得到頂點的入度 十字鏈表 鏈表 1. 空間要求較小 結構較復雜 同鄰接表 2.易求得頂點的出度和入度 鄰接多重表 鏈表 1. 節省空間 結構較復雜 同鄰接表 2. 易判斷兩點間的關系 目前,對于算法中快速搜索技術的實現，主要有桶結構法、隊列法以及堆棧實現法。TQQ、DKA 以及 DKD 在這方面是比較典型的代表。TQQ雖然是基于圖增長理論的，但是快速搜索技術同樣是其算法實現的關鍵，它用兩個FIFO的隊列實現了一個雙端隊

12、列結構來支持搜索過程1。DKA和DKD是采用如圖 1 所示的桶結構來支持這個運算，其算法的命名也來源于此。在DKA算法中，第i個桶內裝有權值落在 b*i, (i+1)*b) 范圍內的可供掃描的點，其中b是視網絡中邊的權值分布情況而定的一個常數。每一個桶用隊列來維護，這樣每個點有可能被多次掃描，但最多次數不會超過b次。最壞情況下，DKA的時間復雜度將會是O(m*b+n(b+C/b)，其中，C為圖中邊的最大權值。DKD將點按權值的范圍大小分裝在兩個級別的桶內，高級別的桶保存權值較大的點，相應的權值較小的點都放在低級別的桶內，每次掃描都只針對低級別桶中的點。當然隨著點的插入和刪除，兩個桶內的點是需要

13、動態調整的。在DKA算法中，給每個桶一定的范圍以及DKD中使用雙桶，在一定程度上都是以空間換時間的做法，需要改進。 圖 1一個桶結構的示例Fig. 1An Example of the Bucket Data Structure 3本文提出的Dijkstra算法實現3.1網絡拓撲關系的建立上面介紹的各種圖的存儲結構考慮了圖在理論上的各種特征，如有向、無向、帶權、出度、入度等。而GIS中的網絡一般為各種道路、管網、管線等，這些網絡在具有圖理論中的基本特征的同時，更具有自己在實際中的一些特點。首先，在GIS中大多數網絡都是有向帶權圖，如道路有單雙向問題，電流、水流都有方向（如果是無向圖也可歸為有向

14、圖的特例），且不同的方向可能有不同的權值。更重要的一點是，根據最短路徑算法的特性可以知道，頂點的出度是個重要指標，但是其入度在算法里則不必考慮。綜合以上4種存儲結構的優缺點， 筆者采用了兩個數組來存儲網絡圖，一個用來存儲和弧段相關的數據（Net-Arc List），另一個則存儲和頂點相關的數據（Net-Node Index）。Net-Arc List用一個數組維護并且以以弧段起點的點號來順序排列，同一起點的弧段可以任意排序。這個數組類似于鄰接矩陣的壓縮存儲方式，其內容則具有鄰接多重表的特點，即一條邊以兩頂點表示。Net-Node Index則相當于一個記錄了頂點出度的索引表，通過它可以很容易地

15、得到此頂點的出度以及與它相連的第一條弧段在弧段數組中的位置。此外，屬性數據作為GIS不可少的一部分也是必須記錄的。這樣，計算最佳路徑所需的網絡信息已經完備了。在頂點已編號的情況下，建立Net-Arc List和Net-Node Index兩個表以及對Net-Arc List的排序，其時間復雜度共為O(2n+lgn)，否則為O(m+2n+lgn)。這個結構所需的空間也是必要條件下最小的，記錄了m個頂點以及n條邊的相關信息，與鄰接多重表是相同的。圖 2 是采用這個結構的示意圖。3.2快速搜索技術的實現無論何種算法，一個基本思想都是將點按權值的大小順序排列，以節省操作時間。前面已經提到過，這兩個算法

16、都是以時間換空間的算法，所以在這里有必要討論存儲空間問題 (這部分空間的大小依賴于點的個數及其出度)。根據圖中頂點和邊的個數可以求出頂點的平均出度e=m/n（m為邊數，n為頂點數），這個數值代表了圖的連通程度，一般在GIS的網絡圖中，e2,5。這樣,如果當前永久標記的點為t個，那么，下一步需掃描點的個數就約為t4t個。如果采用鏈表結構，按實際應用中的網絡規模大小，所需的總存儲空間一般不會超過100 K。所以完全沒有必要采用以時間換空間的做法，相反以空間換時間的做法是完全可行的。在實現這部分時，筆者采用了一個FIFO隊列，相應的操作主要是插入、排序和刪除，插入和刪除的時間復雜度都是O(1)，所以

17、關鍵問題在于選擇一個合適的排序算法。一般可供選擇的排序算法有快速排序、堆排序以及歸并排序等，其實現的平均時間都為O(nlgn)。經過比較實驗，筆者選擇了快速排序法。另外，Visual C+提供的run-time庫也提供了現成的快速排序的函數qsort()可供使用。 圖 2基于最佳路徑計算的網絡拓撲表示Fig. 2The Presentation of the Network TopologyUsed for Computing the Shortest Path 按照以上思路，筆者用Visual C+實現了吉奧之星（GeoStar）中的最佳路徑模塊。以北京的街道為數據（共6 313個結點，9 214條弧段(雙向)），在主頻為133、硬盤為1 G、內存為32 M的機器上，計算一條貫穿全城、長為155.06 km的線路，約需1 s2 s。如圖 3所示。 圖 3GeoStar中最佳路徑實現示意圖Fig. 3The Shortest Path in GeoStar 參考文獻1Zhan F B. Three Fastest Shortest Path Algorithms o