楊志勇 ，葉馮彬 ，馮艷輝 ，劉秀秀 ，朱 巖

（1.中國科學院大學 北京 100049；2.中國科學院國家空間科學中心 北京 100190；3.成都理工大學 成都610059）

有向非負權(quán)圖中經(jīng)過必經(jīng)節(jié)點集最短路徑算法

楊志勇1，2，葉馮彬3，馮艷輝1，2，劉秀秀1，2，朱 巖2

（1.中國科學院大學 北京 100049；2.中國科學院國家空間科學中心 北京 100190；3.成都理工大學 成都610059）

傳統(tǒng)的Dijkstra算法只是針對起點和終點求解最短路徑，而不能解決從起點出發(fā)，經(jīng)過必經(jīng)節(jié)點集，到達終點的無重復(fù)節(jié)點且無回路的最短路徑問題。為此，在有向非負權(quán)圖中，提出了Dijkstra算法和回溯法相結(jié)合的方法。對Dijkstra算法改進，并求解關(guān)鍵節(jié)點（起點，終點和必經(jīng)節(jié)點）間的最短路徑，進而從關(guān)鍵節(jié)點所構(gòu)成的矩陣中采用回溯法得到目標路徑。通過實際的算法實現(xiàn)，測試大量的有向非負權(quán)圖數(shù)據(jù)，證實了算法的有效性和正確性。

Dijkstra算法；回溯法；深度優(yōu)先搜索；最短路徑；必經(jīng)節(jié)點集；有向非負權(quán)圖

最短路徑（SP）算法，可以用來解決道路設(shè)計和網(wǎng)絡(luò)路由等諸多動態(tài)規(guī)劃和優(yōu)化的問題。EW.A Dijkstra于1959年提出著名的Dijkstra算法[1]，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑，其主要思想是以起點為中心向外一層一層輻射迭代，直到輻射到終點為止。

以Dijkstra為原型，研究人員提出了對最短路徑問題[2-4]的諸多優(yōu)化方案。針對Dijkstra算法的復(fù)雜性，提出一種新的時空復(fù)雜度更低的改進算法[5-7]；采用配對堆結(jié)構(gòu)實現(xiàn)路徑計算過程中的優(yōu)先級隊列的一系列操作，提高算法的效率和性能[8]；對Dijkstra標號法改進，實現(xiàn)起點和終點之間的最短路徑[9]；通過對每個頂點增加前置鄰結(jié)點屬性，并實時記錄和更新，求解多條路徑問題[10]。

以上算法是針對只有起點和終點的研究，而生活中還存在一類有待研究又有著重要意義的問題：1）網(wǎng)絡(luò)路由經(jīng)過必經(jīng)路由節(jié)點問題。網(wǎng)絡(luò)數(shù)據(jù)包發(fā)出后，必須經(jīng)過幾個關(guān)鍵路由節(jié)點，這些關(guān)鍵路由節(jié)點需要對網(wǎng)路數(shù)據(jù)包進行審查。2）公交線路設(shè)計問題。設(shè)計一條公交線路，使得公交車從始站出發(fā)，經(jīng)過重要的站點到達終點站的行駛路徑最短[11]。如，逐漸擴大占地面積的校園中，教學樓、學生宿舍、餐廳、體育場更加分散。因此，需要設(shè)計一條便捷的交通線，以節(jié)省校園師生路途時間[12]。3）軍事運輸路徑尋優(yōu)問題。設(shè)計一條軍事人員及物質(zhì)運輸線路，該線路必須通過一些重要的城市、橋梁、加油站、彈藥庫等地點，以滿足作戰(zhàn)需求[13]。

1 問題描述

如圖1所示，求解以0為起點，經(jīng)過必經(jīng)節(jié)點2、3節(jié)點，到達終點1的最短無重復(fù)節(jié)點的路徑。

圖1 4個節(jié)點有向帶權(quán)拓撲圖

以0為起點，經(jīng)過2、3節(jié)點到達終點1的路徑有：0-＞2-＞3-＞1，權(quán)值為4；0-＞3-＞2-＞1，權(quán)值為5。因此，最短路徑為0-＞2-＞3-＞1。

1.1 概念定義

必經(jīng)節(jié)點：最短路徑中必須包含的節(jié)點。

關(guān)鍵節(jié)點：起點、終點和必經(jīng)節(jié)點統(tǒng)稱關(guān)鍵節(jié)點。

自由節(jié)點[14]：除關(guān)鍵節(jié)點以外的其他節(jié)點。

弧頭節(jié)點：指的是有向邊的目標節(jié)點。

弧尾節(jié)點：指的是有向邊的源節(jié)點。

1.2 問題定義

在一個有向非負權(quán)稀疏圖中，給定任意的起點，必經(jīng)節(jié)點和任意終點。要求尋找一條從起點出發(fā)，經(jīng)過所有必經(jīng)節(jié)點，到達終點的無重復(fù)節(jié)點無回路的最短路徑。在這條最短路徑中，可能會經(jīng)過網(wǎng)絡(luò)中除起點、終點和必經(jīng)節(jié)點以外的自由節(jié)點。

2 必經(jīng)節(jié)點最短路徑問題算法分析

文中將龐大的稀疏圖，分解成幾個易于求解的子問題，然后再全局求解最短路徑。因此，對求解稀疏圖必經(jīng)節(jié)點的最短路徑問題，可以分解為兩個過程：1）求解關(guān)鍵節(jié)點間的最短路徑，將龐大的有向非負權(quán)稀疏圖簡化為關(guān)鍵節(jié)點間的稠密圖（關(guān)鍵節(jié)點到關(guān)鍵節(jié)點的路徑上的自由節(jié)點隱藏）；2）在關(guān)鍵節(jié)點間的稠密圖中，尋找一條從起點出發(fā)經(jīng)過所有必經(jīng)節(jié)點到達終點，且無重復(fù)節(jié)點無回路的最短路徑。

3 關(guān)鍵節(jié)點間最短路徑

所謂關(guān)鍵節(jié)點間的最短路徑，就是求解所有關(guān)鍵節(jié)點到其他關(guān)鍵節(jié)點的最短路徑，某一個關(guān)鍵節(jié)點到其他某一個關(guān)鍵節(jié)點的最短路徑中無其他關(guān)鍵節(jié)點。例如，設(shè)關(guān)鍵節(jié)點A、B、C、D，則A到B的路徑中，不包含其他的關(guān)鍵節(jié)點C和D，且該條路徑中無重復(fù)的自由節(jié)點。

文中采用了鄰接鏈表的存儲方式，并在求解關(guān)鍵節(jié)點間的最短路徑時，阻止遇到的關(guān)鍵節(jié)點向外輻射的方式對Dijkstra算法改進，實現(xiàn)將所有稀疏網(wǎng)絡(luò)圖中的節(jié)點簡化成所有關(guān)鍵節(jié)點間的最短路徑稠密圖。

3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

1）存儲網(wǎng)絡(luò)圖的鄰接鏈表數(shù)據(jù)結(jié)構(gòu)

2）dijkstra算法計算時的輔助結(jié)構(gòu)

3）存儲關(guān)鍵節(jié)點間最短路徑的數(shù)據(jù)結(jié)構(gòu)

3.2 關(guān)鍵節(jié)點間最短路徑算法實現(xiàn)步驟

1）將節(jié)點的信息讀取到圖數(shù)據(jù)結(jié)構(gòu)體中；為所有輔助節(jié)點結(jié)構(gòu)分配內(nèi)存空間。

2）將每個單點輔助結(jié)構(gòu)進行初始化：a）currentID設(shè)置為該單點的序號；b）passed設(shè)置為false（表示未經(jīng)過）；c）weight設(shè)置為無窮大（表示不可達）；d）parent設(shè)置為-1（表示為沒有父節(jié)點）。

3）選定一個沒有計算過且非終點的關(guān)鍵節(jié)點作為改進版的 Dijkstra運算的源節(jié)點SourceKeyVertex，作為Dijkstra計算的擴展節(jié)點，并將與關(guān)鍵節(jié)點ID一致的單點輔助結(jié)構(gòu)初始化：a）passed設(shè)置為true（表示經(jīng)過）；b）weight設(shè)置為0（表示起點）；c）parent設(shè)置為-1（表示為沒有父節(jié)點）。

4）更新與當前擴展節(jié)點相連的所有弧頭節(jié)點在輔助結(jié)構(gòu)中的信息，滿足以下條件的節(jié)點更新：a）該弧頭節(jié)點未經(jīng)過；b）源關(guān)鍵節(jié)點到擴展節(jié)點的權(quán)值與當前擴展節(jié)點到弧頭節(jié)點的權(quán)值之和newWeight小于之前對該弧頭節(jié)點更新的權(quán)值oldWeight；c）該弧頭節(jié)點不是起點。

更新內(nèi)容包括：a）弧頭節(jié)點的權(quán)值更新為newWeight值；b）弧頭節(jié)點的父節(jié)點更新為當前擴展節(jié)點。

5）在輔助結(jié)構(gòu)中尋找新的擴展節(jié)點，步驟如下：a）從輔助結(jié)構(gòu)中找到未經(jīng)過的、有后繼節(jié)點且權(quán)值最小的節(jié)點expandVertexTmp。若expandVertexTmp為關(guān)鍵節(jié)點，那么設(shè)置expandVertexTmp為經(jīng)過，即設(shè)置passed為true，重復(fù)當前步驟；若expandVertexTmp為自由節(jié)點，則將expand-VertexTmp作為新的擴展節(jié)點，并將passed設(shè)置為true，重復(fù)第4步驟。b）若未找到符合要求的最小權(quán)值的節(jié)點，那么本輪以關(guān)鍵節(jié)點SourceKeyVertex作為源節(jié)點的Dijkstra的運算結(jié)束，轉(zhuǎn)到第6步驟。

6）在所有關(guān)鍵節(jié)點到關(guān)鍵節(jié)點信息的數(shù)據(jù)結(jié)構(gòu)KeyVertexInfo中，找到與SourceKeyVertex的ID相同的位置，存儲SourceKeyVertex到其他關(guān)鍵節(jié)點的路徑信息。重復(fù)步驟2，繼續(xù)選定一個未計算過且非終點的關(guān)鍵節(jié)點，計算到其他關(guān)鍵節(jié)點的路徑，直到所有的關(guān)鍵節(jié)點都計算了到其他關(guān)鍵節(jié)點的路徑為止。

4 經(jīng)過所有關(guān)鍵節(jié)點的最短路徑

稀疏圖轉(zhuǎn)換為關(guān)鍵節(jié)點間的鏈接稠密圖后，這就轉(zhuǎn)換為查找一條從起點出發(fā)，經(jīng)過所有的必經(jīng)節(jié)點，到達終點的最小權(quán)值路徑問題。

4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

1）采用計算關(guān)鍵節(jié)點間最短路徑的數(shù)據(jù)結(jié)構(gòu)。

2）深度優(yōu)先搜索時不作為擴展節(jié)點的關(guān)鍵節(jié)點信息存儲棧。

std::stack＜Assist＞ onePointAssistStack；

3）深度優(yōu)先搜索時所找到的一條最短路徑的存儲結(jié)構(gòu)。

std::stack＜unsigned int＞ minWeightPath；

4.2 經(jīng)過所有關(guān)鍵節(jié)點的算法實現(xiàn)步驟

1）初始化每個單點輔助結(jié)構(gòu)，將起點作為擴展節(jié)點，并設(shè)置起點的相應(yīng)信息，與改進Dijkstra運算中的步驟2、步驟3相同。

2）判定是否經(jīng)過了所有的關(guān)鍵節(jié)點，新的擴展節(jié)點為終點，并且到達終點的權(quán)值比之前到達的權(quán)值小。a）若滿足要求，則清空minWeightPath存儲結(jié)構(gòu)中的路徑信息，并存儲該條路徑中的所有節(jié)點（關(guān)鍵節(jié)點和自由節(jié)點）編號。轉(zhuǎn)到第4步驟。b）若不滿足要求，轉(zhuǎn)到第3步驟。

3）查找一個新的擴展節(jié)點（關(guān)鍵節(jié)點）。判定當前擴展節(jié)點到其他關(guān)鍵節(jié)點路徑的有效性，即到其他關(guān)鍵節(jié)點的路徑上的自由節(jié)點不在起點到達當前擴展節(jié)點路徑中；所判定的關(guān)鍵節(jié)點未經(jīng)過；未提前到達終點；到所判定的關(guān)鍵節(jié)點的權(quán)值未超過已有路徑的最小權(quán)值：a）若擴展節(jié)點到其他的關(guān)鍵節(jié)點有效，將當前擴展節(jié)點到新的擴展節(jié)點路徑中的自由節(jié)點更新為經(jīng)過，以及更新相應(yīng)的父節(jié)點值。并將第一個有效的關(guān)鍵節(jié)點作為新的擴展節(jié)點，其他有效的關(guān)鍵節(jié)點壓入關(guān)鍵信息存儲棧中，重復(fù)第3步驟。b）若擴展節(jié)點到其他的關(guān)鍵節(jié)都無效，轉(zhuǎn)到第4步驟。

4）判定關(guān)鍵信息存儲棧是否為空。a）若棧為空，結(jié)束回溯深度優(yōu)先搜索算法；b）若棧不為空，從關(guān)鍵信息存儲棧中彈出一個關(guān)鍵節(jié)點，并將該關(guān)鍵節(jié)點作為新的擴展節(jié)點。將原擴展節(jié)點（關(guān)鍵節(jié)點）到新擴展節(jié)點的父節(jié)點所在路徑上的節(jié)點的信息設(shè)置為未經(jīng)過；更新新擴展節(jié)點在輔助結(jié)構(gòu)中的狀態(tài)；更新新擴展節(jié)點到其父節(jié)點（關(guān)鍵節(jié)點）路徑上的自由節(jié)點的狀態(tài)。重復(fù)第2步驟。

回溯深度優(yōu)先搜索過程，步驟3判定節(jié)點的有效性保證了所求得的路徑中無重復(fù)節(jié)點無回路?；厮萆疃葍?yōu)先搜索的方式保證了搜索出來的結(jié)果肯定是滿足條件且全局最優(yōu)的結(jié)果，即該條路徑是從起點出發(fā)，經(jīng)過所有的必經(jīng)節(jié)點，到達終點無重復(fù)節(jié)點無回路的最短路徑。

5 算法實例測試

算法運行環(huán)境為Ubuntu14.04.132bits系統(tǒng)，2.2GHz T6670CPU，3GB內(nèi)存，編程語言C++，編譯器為GCC4.8.2（編譯時采用O2優(yōu)化）。算法測試用例均來自2016華為軟件精英挑戰(zhàn)賽初賽[15]試題提供的數(shù)據(jù)。

挑戰(zhàn)賽的題目：給定一個帶權(quán)重的有向圖G=（V，E），V 為頂點集（頂點不超過 600 個，每個頂點的出度不超過8），E為有向邊集，每一條有向邊均有一個權(quán)重。對于給定的頂點s、t，以及V的子集V'（元素個數(shù)不超過50），尋找s到t的不成環(huán)有向路徑P，使得P經(jīng)過V'中所有的頂點[14]。

5.1 程序運行中間結(jié)果

本實驗從文獻[15]所提供的數(shù)據(jù)中，選取測試用例觀察程序運行的中間結(jié)果。為了降低檢驗中間結(jié)果的復(fù)雜性，該測試實例選用在20個節(jié)點中，起點為2，終點為19，必經(jīng)節(jié)點為3、5、7、11、13、17，找出一條經(jīng)過必經(jīng)節(jié)點的最短路徑，網(wǎng)路節(jié)點數(shù)據(jù)所形成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖2所示。

圖2 20個節(jié)點的有向帶權(quán)拓撲圖

通過Dijkstra運算后，關(guān)鍵節(jié)點間的路徑如表2所示。關(guān)鍵節(jié)點間的權(quán)重值的稠密矩陣關(guān)系如表3所示。其中，關(guān)鍵節(jié)點間的簡化鏈接，可能是經(jīng)過自由節(jié)點才能到達的。

表1 關(guān)鍵節(jié)點間的路徑

以表1的第一行為例，表示的關(guān)鍵點2到關(guān)鍵點3的最短路徑權(quán)值為18，其中需要經(jīng)過自由節(jié)點15和18。Path中沒有自由節(jié)點，表示的是源關(guān)鍵節(jié)點直達目標關(guān)鍵節(jié)點。

表2 關(guān)鍵節(jié)點間的權(quán)值稠密矩陣

以表2的第二行為例，表示的是關(guān)鍵節(jié)點3到達其他關(guān)鍵節(jié)點的情況。其中，能夠到 5、11、13、17和19共5個關(guān)鍵節(jié)點；不可達的關(guān)鍵節(jié)點為2和7。

轉(zhuǎn)換成稠密矩陣之后，采用回溯深度優(yōu)先搜索的方式進行搜索，最短路徑（權(quán)值71）如下：

2-＞15-＞18-＞3-＞11-＞7-＞13-＞4-＞5-＞6-＞17-＞19

中間結(jié)果的總體觀察結(jié)果，表明該算法能夠準確的找出滿足條件的最短路徑，且無重復(fù)節(jié)點。

5.2 測試在不同節(jié)點下運行的時間效率

在計算關(guān)鍵節(jié)點間的最短路徑和計算得到最終結(jié)果處設(shè)置計時器，記錄計算節(jié)點間最短路徑的平均花費時間和找到最短路徑時總的平均花費時間。由于文獻[15]所提供的數(shù)據(jù)的最大節(jié)點個數(shù)為600個節(jié)點。因此，設(shè)定測試節(jié)點總數(shù)分別為180個，300個和600個，并且設(shè)置必經(jīng)節(jié)點數(shù)目為10個、15個和20個。多組數(shù)據(jù)測試平均結(jié)果如表3～5所示。

表3 180個節(jié)點數(shù)運行時間

表4 300個節(jié)點數(shù)運行時間

表5 600個節(jié)點數(shù)運行時間

從測試結(jié)果可以看出，對于龐大的網(wǎng)絡(luò)圖中，必經(jīng)節(jié)點數(shù)目較少時，程序運行的時間非常的可觀，比文獻[14]中的運行時間縮短了幾十倍。

6 算法復(fù)雜度分析

在計算關(guān)鍵節(jié)點間的最短路徑時，采用的是傳統(tǒng)的實現(xiàn)方式。理論上該算法的時間復(fù)雜度為。但在計算關(guān)鍵節(jié)點間的最短路徑時采用遇到關(guān)鍵節(jié)點直接終止關(guān)鍵節(jié)點向外輻射的方式[16]，大大減少擴展節(jié)點向外輻射的鏈接數(shù)，使算法更加快速的收斂，降低算法運算的復(fù)雜度。測試結(jié)果表明，在計算關(guān)鍵節(jié)點間的最短路徑所需要花費的時間對總節(jié)點數(shù)和中間節(jié)點數(shù)都不敏感。只是在回溯深度優(yōu)先搜索查找經(jīng)過所有關(guān)鍵節(jié)點的最短路徑時，對必經(jīng)節(jié)點個數(shù)非常敏感。必經(jīng)節(jié)點數(shù)增加，將按照階乘的方式增加，運算量很大。因此，在關(guān)鍵節(jié)點數(shù)不超過回溯深度優(yōu)先搜索接受范圍內(nèi)，也能快速的對整個稠密圖的最短路徑查找。該算法只能針對較少關(guān)鍵節(jié)點數(shù)的問題，在以后的研究中可以重點研究關(guān)鍵節(jié)點間查找最短路徑問題。

7 結(jié)束語

對于網(wǎng)絡(luò)路由經(jīng)過必經(jīng)路由節(jié)點問題和公交線路設(shè)計問題，都可以采用將龐大的有向稀疏圖簡化成關(guān)鍵節(jié)點的稠密圖，并搜索得到滿足條件的最短路徑的方法進行求解?？偟膩碚f，該算法面對大規(guī)模的有向稀疏網(wǎng)絡(luò)圖，提出了新的求解最短路徑問題的算法思想。但還需要進一步的研究和改進該算法，以解決海量的網(wǎng)絡(luò)節(jié)點數(shù)和大量的必經(jīng)節(jié)點數(shù)情況下的最短路徑問題。

[1]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959（1）:269-271.

[2]李娟，張婷，李元香.基于改進演化算法的最短路徑問題研究[J].計算機應(yīng)用與軟件，2015，32（9）:244-245，273.

[3]劉荷花，翟超，陳晶.一種改進的遺傳算法求解旅行商問題[J].北京理工大學學報，2013（12）:139-142.

[4]牟銜臣，謝東來，閆威，等.基于遺傳算法航路規(guī)劃TSP問題的研究[J].系統(tǒng)仿真學報，2013:190-196.

[5]張錦明，洪剛，文銳，等.Dijkstra最短路徑算法優(yōu)化策略[J].測繪科學，2009，34（5）:105-106，99.

[6]Orlin JB，Madduri K，Subramani K，et al.A faster algorithm forthe single source shortestpath problem withfew distinct positivelengths[J].Journal of Discrete Algorithms，2010，8（2）:189-198.

[7]王智廣，王興會，李妍.一種基于Dijkstra最短路徑算法的改進算法[J].內(nèi)蒙古師范大學學報，2012，41（2）:195-200.

[8]王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實現(xiàn)[J].微計算機信息，2007，23（11）:275-277.

[9]王樹西，吳政學.改進的Dijkstra最短路徑算法及其應(yīng)用研究[J].計算機科學，2012，39（5）:223-228.

[10]金婷，方歡，方賢文.改進型Dijkstra算法的最短路徑求解[J].軟件導刊，2016，15（2）:129-131.

[11]姚廣錚，孫壯志，孫福亮，等.北京奧運公交專線規(guī)劃及評價方法[J].城市交通，2008，6（3）:29-34.

[12]薛瑞，張永顯.校車最優(yōu)路徑規(guī)劃算法研究[J].重慶科技學院學報：自然科學報，2015，17（5）:68-71.

[13]徐慶征，柯熙政.必經(jīng)點最短路徑問題模型及相應(yīng)遺傳算法研究[J].系統(tǒng)工程與電子技術(shù)，2009，31（2）:459-462.

[14]黃書力，胡大裟，蔣玉明.經(jīng)過指定的中間節(jié)點集的最短路徑算法[J].計算機工程與應(yīng)用，2015，51（11）:41-46.

[15]2016華為精英挑戰(zhàn)賽初賽試題[EB/OL].（2016-03-04）[2016-04-27].http://codecraft.huawei.com/home/detail.

[16]熊揚宇，宋鵬，王建余，等.紫外光通信網(wǎng)節(jié)點設(shè)計與性能分析[J].西安工程大學學報，2016，30（6）：797-801.

Algorithm for finding shortest path which contains a necessary set of nodes in directed and non-negative weighted graph

YANG Zhi-yong1，2，YE Feng-bin3，F(xiàn)ENG Yan-hui1，2，LIU Xiu-xiu1，2，ZHU Yan2
（1.University of Chinese Academy of Sciences，Beijing 100049，China；2.National Space Science Center of Chinese Academy of Sciences，Beijing 100190，China；3.Chengdu University of Technology，Chengdu 610059，China）

Traditional Dijkstra algorithm can get the shortest path with start and end，but it can not gain the shortest path which starts from start，goes through the necessary set of nodes and arrivals the end without duplication and loop.Therefore，put forward the idea to combine Dijkstra algorithm and backtracking algorithm in directed and non-negative weighted graph.Using the improved Dijkstra algorithm solved the shortest path between the key nodes（including start，end and the necessary set of nodes）.And then，backtracking algorithm with depth-first search methodobtained the target path from the matrix composed of key nodes.The result confirms the validity and correctness by testing a large of directed and non-negative weighted graph data with code of the algorithm.

Dijkstra algorithm；backtracking algorithm；depth-first search method； shortest path； a necessary set of nodes；directed and non-negative weighted graph

TP393

A

1674－6236（2017）16-0032-05

2016-06-29稿件編號：201606224

楊志勇（1990—），男，四川仁壽人，碩士研究生。研究方向：信息獲取與處理、計算機網(wǎng)絡(luò)路由。