李寬榮　陸通　高勇

摘 要：最短路徑分析是網(wǎng)絡(luò)拓?fù)渲械囊粋€(gè)重要的應(yīng)用，它在地理信息系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)路由等方面發(fā)揮著至關(guān)重要的作用。解決最短路徑問(wèn)題的經(jīng)典方法是Dijkstra算法，時(shí)間復(fù)雜度為O（n2），在大數(shù)據(jù)量下效率低下而且使用鄰接矩陣存儲(chǔ)圖形數(shù)據(jù)在一定程度上造成了空間浪費(fèi)。該文在分析了Dijkstra算法的基礎(chǔ)上提出來(lái)一種改進(jìn)方法，該法使用STL容器來(lái)代替鄰接矩陣來(lái)存儲(chǔ)圖形數(shù)據(jù)提高了查詢(xún)效率，并且利用雙隊(duì)列來(lái)存儲(chǔ)節(jié)點(diǎn)降低了內(nèi)循環(huán)次數(shù)，減少了很多不必要的計(jì)算，從而降低了算法時(shí)間復(fù)雜度。STL容器的應(yīng)用使得最短路徑算法得到了擴(kuò)展，在求解最短路徑的同時(shí)還支持添加障礙點(diǎn)，增加開(kāi)關(guān)節(jié)點(diǎn)等應(yīng)用。

關(guān)鍵詞：最短路徑分析 Dijkstra STL

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）04（c）-0037-02

Dijkstra算法的最大不足之處是在于求解的是一點(diǎn)到網(wǎng)絡(luò)中所有點(diǎn)的最短距離，而實(shí)際應(yīng)用中更多的是求解指定兩點(diǎn)之間的最短距離。求解到所有點(diǎn)的距離完全沒(méi)有必要，從計(jì)算代價(jià)來(lái)講也是一種極大的浪費(fèi)。Dijkstra 算法中使用矩陣來(lái)存儲(chǔ)圖像數(shù)據(jù)，對(duì)于有N個(gè)節(jié)點(diǎn)的圖形，需要存儲(chǔ)N*N個(gè)數(shù)據(jù)，雖然可以使用對(duì)稱(chēng)性來(lái)減少數(shù)量，但在大數(shù)據(jù)量下仍不能很好解決問(wèn)題。目前，很多基于Dijstra的算法都是在數(shù)據(jù)結(jié)構(gòu)和分析效率兩個(gè)方面來(lái)優(yōu)化。

該文在分析了Dijkstra算法的基礎(chǔ)上，利用STL的map和multimap容器來(lái)存儲(chǔ)圖形數(shù)據(jù)，方便了數(shù)據(jù)的存取，也節(jié)省了內(nèi)存占用。在求解的過(guò)程中使用兩個(gè)優(yōu)先級(jí)隊(duì)列來(lái)存儲(chǔ)待處理的節(jié)點(diǎn)，減少了內(nèi)循環(huán)次數(shù)，降低了算法的時(shí)間復(fù)雜度。同時(shí)，引入STL map作狀態(tài)容器，使其支持對(duì)障礙點(diǎn)的分析。而STL multimap的引入又可以使原有的節(jié)點(diǎn)增加開(kāi)關(guān)屬性，從而支持對(duì)電力拓?fù)渚W(wǎng)絡(luò)的分析。

1 Dijkstra算法優(yōu)化

1.1 存儲(chǔ)圖形數(shù)據(jù)

由于網(wǎng)絡(luò)中的節(jié)點(diǎn)之間的關(guān)系是多對(duì)多的關(guān)系，每一個(gè)節(jié)點(diǎn)可能關(guān)聯(lián)多個(gè)節(jié)點(diǎn)，所以使用STL multimap來(lái)存儲(chǔ)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系。同時(shí)，為每一個(gè)節(jié)點(diǎn)建立一個(gè)狀態(tài)標(biāo)志，使用STL map來(lái)存儲(chǔ)。Multimap和map使用的是紅黑樹(shù)結(jié)構(gòu)來(lái)存儲(chǔ)節(jié)點(diǎn)，所以具有較高的查詢(xún)效率，而且內(nèi)存空間是動(dòng)態(tài)擴(kuò)展的不需要事先計(jì)算需要的內(nèi)存空間，能很好的解決從數(shù)據(jù)庫(kù)中讀取未知數(shù)量的數(shù)據(jù)的情況。

另外，multimap支持結(jié)構(gòu)體來(lái)作鍵值，所以可以存儲(chǔ)更多信息。比如，考慮到電力網(wǎng)絡(luò)的節(jié)點(diǎn)，可以存儲(chǔ)開(kāi)關(guān)節(jié)點(diǎn)的狀態(tài)信息。Dijkstra算法只是求解最短路徑長(zhǎng)度，但并不能得到具體的路徑。而使用map來(lái)存儲(chǔ)節(jié)點(diǎn)的狀態(tài)信息StateInfo，可以用一個(gè)標(biāo)識(shí)來(lái)記錄最短路徑上每個(gè)節(jié)點(diǎn)的前一節(jié)點(diǎn)。這樣通過(guò)從目的點(diǎn)開(kāi)始依次查詢(xún)其前一節(jié)點(diǎn)直到起始點(diǎn)就能獲取最短路徑。StateInfo的引用使得求解最短距離算法得到進(jìn)一步的擴(kuò)展，比如，可以設(shè)置障礙點(diǎn)，所求的最短距離必須繞過(guò)障礙點(diǎn)。只需要設(shè)置給障礙點(diǎn)設(shè)置一個(gè)新的狀態(tài)，就可以實(shí)現(xiàn)。

1.2 雙隊(duì)列的應(yīng)用

另外一種數(shù)據(jù)結(jié)構(gòu)是隊(duì)列，用來(lái)存儲(chǔ)即將進(jìn)行探測(cè)的節(jié)點(diǎn)。本文中用了兩個(gè)隊(duì)列，并以?xún)?yōu)先級(jí)的高低區(qū)分。高優(yōu)先級(jí)隊(duì)列存放已經(jīng)探測(cè)過(guò)但是最短路徑需要更新的節(jié)點(diǎn)，低優(yōu)先級(jí)隊(duì)列存放第一次探測(cè)到的節(jié)點(diǎn)。高優(yōu)先級(jí)的隊(duì)列中的節(jié)點(diǎn)會(huì)被優(yōu)先取出進(jìn)行探測(cè)，因?yàn)楦邇?yōu)先級(jí)節(jié)點(diǎn)有更高的概率到達(dá)目標(biāo)節(jié)點(diǎn)。

1.3 高效算法的提出

為了進(jìn)一步的提高計(jì)算速度，采用雙隊(duì)列來(lái)存儲(chǔ)當(dāng)前計(jì)算的節(jié)點(diǎn)信息，一個(gè)是高優(yōu)先級(jí)對(duì)列HighQueue，一個(gè)是低優(yōu)先級(jí)隊(duì)列LowQueue?；静襟E如下：

（1）首先，利用STL multimap和map定義數(shù)據(jù)結(jié)構(gòu)JointRealtionInfo，StateInfo來(lái)存儲(chǔ)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系和狀態(tài)信息。然后，讀取數(shù)據(jù)庫(kù)信息到數(shù)據(jù)結(jié)構(gòu)中，設(shè)定每個(gè)節(jié)點(diǎn)的狀態(tài)信息初始值為Unchecked。

（2）定義兩個(gè)隊(duì)列：HighQueue、LowQueue，并將起始節(jié)點(diǎn)srcJointID加入LowQueue中，同時(shí)修改StateInfo中起點(diǎn)的狀態(tài)StateInfo[srcJointID].state =checking，修改長(zhǎng)度標(biāo)簽為0，表示當(dāng)前節(jié)點(diǎn)距離起始節(jié)點(diǎn)的距離為0。

（3）判斷HighQueue或LowQueue是否為空，若都為空，則直接返回終點(diǎn)節(jié)點(diǎn)DesJoint的長(zhǎng)度標(biāo)簽值。若有一個(gè)不為空，則繼續(xù)執(zhí)行下一步。

（4）優(yōu)先判斷HighQueue是否為空，在為空的前提下再判斷LowQueue。無(wú)論如何取不為空的隊(duì)列的第一個(gè)元素值，賦值給臨時(shí)變量TempJoint。

（5）統(tǒng)計(jì)JointRelationInfo中以TempJoint為鍵的個(gè)數(shù)amount（這里使用multimap：：count（）來(lái)統(tǒng)計(jì)）。使用multimap：：find（）來(lái)返回一個(gè)迭代器Iter指向第一個(gè)以TempJoint為鍵的鍵值對(duì)，通過(guò)Iter可以找到對(duì)應(yīng)的值，即與TempJoint相鄰的下一個(gè)節(jié)點(diǎn)的ID，以及TempJoint本身的長(zhǎng)度和開(kāi)關(guān)狀態(tài)，若存在另外一個(gè)相鄰節(jié)點(diǎn)，則使Iter++即能找到，這就是multimap的便利之處。

（6）判斷如果amout>0，首先通過(guò)Iter找出第一個(gè)相鄰的節(jié)點(diǎn)AbutJoint，并獲取其自身的長(zhǎng)度abutLen，將其與TempJointD的距離標(biāo)簽值相加得到NewMarkLen。并與AbutJoint的距離標(biāo)簽值abutMarkLen作比較。若大于，說(shuō)明經(jīng)過(guò)TempJoint到達(dá)AbutJoint的路徑并不比當(dāng)前AbutJoint的路徑短，此時(shí)執(zhí)行步驟（7）。若小于，說(shuō)明經(jīng)過(guò)TempJoint到達(dá)AbutJoint的路徑要比AbutJoint原本的路徑更短。此時(shí)執(zhí)行步驟（8）。如果amount=0，說(shuō)明TempJoint的相鄰節(jié)點(diǎn)都已經(jīng)遍歷完，接下來(lái)執(zhí)行步驟（11）。endprint

（7）使amount--，Iter++，并繼續(xù)執(zhí)行（6）。

（8）首先要判斷TempJoint開(kāi)關(guān)狀態(tài)，若是打開(kāi)，則說(shuō)明此路不通。若是閉合則繼續(xù)。修改AbutJoint的距離標(biāo)簽值為NewMarkLen，同時(shí)將AbutJoint的當(dāng)前路徑上的前一個(gè)節(jié)點(diǎn)priorJoint設(shè)為T(mén)empJoint。判斷AbutJoint當(dāng)前狀態(tài)AbutState，若AbutState=CHECKED，則執(zhí)行步驟（9）。若AbutState=UNCHECKED，則執(zhí)行步驟（10）。

（9）AbutJoint狀態(tài)為CHECKED說(shuō)明已經(jīng)存在從SrcJoint到AbutJoint的路徑，但是經(jīng)過(guò)TempJoint的路徑要比之前的路徑更短，所以需要更新原有的路徑。判斷當(dāng)前的AbutJoint是否是目標(biāo)節(jié)點(diǎn)DesJoint，若不是，則將AbutJoint加入到HighQueue中等待進(jìn)一步的處理。然后，更新AbutJoint的狀態(tài)為CHECKEING。執(zhí)行步驟（7）。

（10）AbutJointz狀態(tài)為UNCHE CKED，說(shuō)明從原點(diǎn)SrcJoint開(kāi)始探測(cè)的路徑尚未有經(jīng)過(guò)AbutJoint。此時(shí)判斷AbutJoint是否是目標(biāo)節(jié)點(diǎn)DesJoint，若不是將其加入到LowQueue中，并修改AbutJoint的狀態(tài)為CHECKING。執(zhí)行步驟（7）。

（11）設(shè)置TempJoint的狀態(tài)為CHECKED，檢測(cè)DesJoint的狀態(tài)，判斷目標(biāo)點(diǎn)DesJoint是否已經(jīng)被探測(cè)到，也就是說(shuō)已經(jīng)存在一條從原點(diǎn)SrcJoint到目標(biāo)點(diǎn)DesJoint的路徑。若DesJoint的狀態(tài)為CHECKING，獲取DesJoint的距離標(biāo)簽DesMarkLen，即SrcJoint到DesJoint的距離，執(zhí)行步驟（12）。若為CHECKED或UNCHECKED，執(zhí)行步驟（3）。

（12）經(jīng)過(guò)上述11個(gè)步驟就可以完成從原點(diǎn)到目標(biāo)點(diǎn)的最短路徑搜索，為了進(jìn)一步的優(yōu)化，當(dāng)目標(biāo)點(diǎn)已經(jīng)找到以后，將其距離標(biāo)簽DesMarkLen與當(dāng)前HighQueue、LowQueue內(nèi)節(jié)點(diǎn)的距離標(biāo)簽進(jìn)行逐一比較，若隊(duì)列中的節(jié)點(diǎn)的距離標(biāo)簽都要比DesMarkLen大，說(shuō)明當(dāng)前找到的起始點(diǎn)到目標(biāo)點(diǎn)的最短路徑即為最短的路徑，不肯能再存在更短的路徑。若隊(duì)列中存在距離標(biāo)簽小于DesMarkLen的節(jié)點(diǎn)，則說(shuō)明有可能存在到達(dá)目標(biāo)節(jié)點(diǎn)更短的路徑，不作任何處理繼續(xù)。

2 結(jié)語(yǔ)

該文通過(guò)使用STL容器來(lái)存儲(chǔ)圖形中節(jié)點(diǎn)之間的關(guān)系，在降低內(nèi)存占用的同時(shí)也加快了查詢(xún)的速度，而且使原有的算法不再是單純的求解兩點(diǎn)之間的最短路徑，還可以增加開(kāi)關(guān)節(jié)點(diǎn)以及對(duì)障礙點(diǎn)的分析。采用高低優(yōu)先級(jí)雙隊(duì)列，分解了算法的規(guī)模，降低了時(shí)間復(fù)雜度，進(jìn)一步提高了求解最短距離的效率。

參考文獻(xiàn)

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

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

[3] 王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實(shí)現(xiàn)[J].微計(jì)算機(jī)信息， 2007，11（3）：275-278.

[4] 寧建紅.最短路徑算法效率研究[J].上海電機(jī)學(xué)院學(xué)報(bào)，2006（3）：38-41.

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