一種基于STL的高效最短路徑算法

李寬榮　陸通　高勇

摘 要：最短路徑分析是網絡拓撲中的一個重要的應用，它在地理信息系統、計算機網絡路由等方面發揮著至關重要的作用。解決最短路徑問題的經典方法是Dijkstra算法，時間復雜度為O（n2），在大數據量下效率低下而且使用鄰接矩陣存儲圖形數據在一定程度上造成了空間浪費。該文在分析了Dijkstra算法的基礎上提出來一種改進方法，該法使用STL容器來代替鄰接矩陣來存儲圖形數據提高了查詢效率，并且利用雙隊列來存儲節點降低了內循環次數，減少了很多不必要的計算，從而降低了算法時間復雜度。STL容器的應用使得最短路徑算法得到了擴展，在求解最短路徑的同時還支持添加障礙點，增加開關節點等應用。

關鍵詞：最短路徑分析 Dijkstra STL

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1674-098X（2014）04（c）-0037-02

Dijkstra算法的最大不足之處是在于求解的是一點到網絡中所有點的最短距離，而實際應用中更多的是求解指定兩點之間的最短距離。求解到所有點的距離完全沒有必要，從計算代價來講也是一種極大的浪費。Dijkstra 算法中使用矩陣來存儲圖像數據，對于有N個節點的圖形，需要存儲N*N個數據，雖然可以使用對稱性來減少數量，但在大數據量下仍不能很好解決問題。目前，很多基于Dijstra的算法都是在數據結構和分析效率兩個方面來優化。

該文在分析了Dijkstra算法的基礎上，利用STL的map和multimap容器來存儲圖形數據，方便了數據的存取，也節省了內存占用。在求解的過程中使用兩個優先級隊列來存儲待處理的節點，減少了內循環次數，降低了算法的時間復雜度。同時，引入STL map作狀態容器，使其支持對障礙點的分析。而STL multimap的引入又可以使原有的節點增加開關屬性，從而支持對電力拓撲網絡的分析。

1 Dijkstra算法優化

1.1 存儲圖形數據

由于網絡中的節點之間的關系是多對多的關系，每一個節點可能關聯多個節點，所以使用STL multimap來存儲節點之間的關聯關系。同時，為每一個節點建立一個狀態標志，使用STL map來存儲。Multimap和map使用的是紅黑樹結構來存儲節點，所以具有較高的查詢效率，而且內存空間是動態擴展的不需要事先計算需要的內存空間，能很好的解決從數據庫中讀取未知數量的數據的情況。

另外，multimap支持結構體來作鍵值，所以可以存儲更多信息。比如，考慮到電力網絡的節點，可以存儲開關節點的狀態信息。Dijkstra算法只是求解最短路徑長度，但并不能得到具體的路徑。而使用map來存儲節點的狀態信息StateInfo，可以用一個標識來記錄最短路徑上每個節點的前一節點。這樣通過從目的點開始依次查詢其前一節點直到起始點就能獲取最短路徑。StateInfo的引用使得求解最短距離算法得到進一步的擴展，比如，可以設置障礙點，所求的最短距離必須繞過障礙點。只需要設置給障礙點設置一個新的狀態，就可以實現。

1.2 雙隊列的應用

另外一種數據結構是隊列，用來存儲即將進行探測的節點。本文中用了兩個隊列，并以優先級的高低區分。高優先級隊列存放已經探測過但是最短路徑需要更新的節點，低優先級隊列存放第一次探測到的節點。高優先級的隊列中的節點會被優先取出進行探測，因為高優先級節點有更高的概率到達目標節點。

1.3 高效算法的提出

為了進一步的提高計算速度，采用雙隊列來存儲當前計算的節點信息，一個是高優先級對列HighQueue，一個是低優先級隊列LowQueue。基本步驟如下：

（1）首先，利用STL multimap和map定義數據結構JointRealtionInfo，StateInfo來存儲節點之間的關聯關系和狀態信息。然后，讀取數據庫信息到數據結構中，設定每個節點的狀態信息初始值為Unchecked。

（2）定義兩個隊列：HighQueue、LowQueue，并將起始節點srcJointID加入LowQueue中，同時修改StateInfo中起點的狀態StateInfo[srcJointID].state =checking，修改長度標簽為0，表示當前節點距離起始節點的距離為0。

（3）判斷HighQueue或LowQueue是否為空，若都為空，則直接返回終點節點DesJoint的長度標簽值。若有一個不為空，則繼續執行下一步。

（4）優先判斷HighQueue是否為空，在為空的前提下再判斷LowQueue。無論如何取不為空的隊列的第一個元素值，賦值給臨時變量TempJoint。

（5）統計JointRelationInfo中以TempJoint為鍵的個數amount（這里使用multimap：：count（）來統計）。使用multimap：：find（）來返回一個迭代器Iter指向第一個以TempJoint為鍵的鍵值對，通過Iter可以找到對應的值，即與TempJoint相鄰的下一個節點的ID，以及TempJoint本身的長度和開關狀態，若存在另外一個相鄰節點，則使Iter++即能找到，這就是multimap的便利之處。

（6）判斷如果amout>0，首先通過Iter找出第一個相鄰的節點AbutJoint，并獲取其自身的長度abutLen，將其與TempJointD的距離標簽值相加得到NewMarkLen。并與AbutJoint的距離標簽值abutMarkLen作比較。若大于，說明經過TempJoint到達AbutJoint的路徑并不比當前AbutJoint的路徑短，此時執行步驟（7）。若小于，說明經過TempJoint到達AbutJoint的路徑要比AbutJoint原本的路徑更短。此時執行步驟（8）。如果amount=0，說明TempJoint的相鄰節點都已經遍歷完，接下來執行步驟（11）。endprint

（7）使amount--，Iter++，并繼續執行（6）。

（8）首先要判斷TempJoint開關狀態，若是打開，則說明此路不通。若是閉合則繼續。修改AbutJoint的距離標簽值為NewMarkLen，同時將AbutJoint的當前路徑上的前一個節點priorJoint設為TempJoint。判斷AbutJoint當前狀態AbutState，若AbutState=CHECKED，則執行步驟（9）。若AbutState=UNCHECKED，則執行步驟（10）。

（9）AbutJoint狀態為CHECKED說明已經存在從SrcJoint到AbutJoint的路徑，但是經過TempJoint的路徑要比之前的路徑更短，所以需要更新原有的路徑。判斷當前的AbutJoint是否是目標節點DesJoint，若不是，則將AbutJoint加入到HighQueue中等待進一步的處理。然后，更新AbutJoint的狀態為CHECKEING。執行步驟（7）。

（10）AbutJointz狀態為UNCHE CKED，說明從原點SrcJoint開始探測的路徑尚未有經過AbutJoint。此時判斷AbutJoint是否是目標節點DesJoint，若不是將其加入到LowQueue中，并修改AbutJoint的狀態為CHECKING。執行步驟（7）。

（11）設置TempJoint的狀態為CHECKED，檢測DesJoint的狀態，判斷目標點DesJoint是否已經被探測到，也就是說已經存在一條從原點SrcJoint到目標點DesJoint的路徑。若DesJoint的狀態為CHECKING，獲取DesJoint的距離標簽DesMarkLen，即SrcJoint到DesJoint的距離，執行步驟（12）。若為CHECKED或UNCHECKED，執行步驟（3）。

（12）經過上述11個步驟就可以完成從原點到目標點的最短路徑搜索，為了進一步的優化，當目標點已經找到以后，將其距離標簽DesMarkLen與當前HighQueue、LowQueue內節點的距離標簽進行逐一比較，若隊列中的節點的距離標簽都要比DesMarkLen大，說明當前找到的起始點到目標點的最短路徑即為最短的路徑，不肯能再存在更短的路徑。若隊列中存在距離標簽小于DesMarkLen的節點，則說明有可能存在到達目標節點更短的路徑，不作任何處理繼續。

2 結語

該文通過使用STL容器來存儲圖形中節點之間的關系，在降低內存占用的同時也加快了查詢的速度，而且使原有的算法不再是單純的求解兩點之間的最短路徑，還可以增加開關節點以及對障礙點的分析。采用高低優先級雙隊列，分解了算法的規模，降低了時間復雜度，進一步提高了求解最短距離的效率。

參考文獻

[1] Stefano. Pallottino. Shortest-path methods： Complexity， interrelations and new propositions[J].Networks，1984（14）.

[2] 侯捷.STL源碼剖析[M].華中科技大學出版社，2002.

[3] 王志和，凌云.Dijkstra最短路徑算法的優化及其實現[J].微計算機信息， 2007，11（3）：275-278.

[4] 寧建紅.最短路徑算法效率研究[J].上海電機學院學報，2006（3）：38-41.

[5] 張紅科.基于鏈表的Dijkstra算法優化研究[J].電腦知識與技術，2008（26）.endprint