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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

圖1 4個節(jié)點(diǎn)有向帶權(quán)拓?fù)鋱D

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

1.1 概念定義

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

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

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

弧頭節(jié)點(diǎn)：指的是有向邊的目標(biāo)節(jié)點(diǎn)。

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

1.2 問題定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

std::stack＜Assist＞ onePointAssistStack；

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

std::stack＜unsigned int＞ minWeightPath；

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

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

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

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

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

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

5 算法實(shí)例測試

算法運(yùn)行環(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 為頂點(diǎn)集（頂點(diǎn)不超過 600 個，每個頂點(diǎn)的出度不超過8），E為有向邊集，每一條有向邊均有一個權(quán)重。對于給定的頂點(diǎn)s、t，以及V的子集V'（元素個數(shù)不超過50），尋找s到t的不成環(huán)有向路徑P，使得P經(jīng)過V'中所有的頂點(diǎn)[14]。

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

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

圖2 20個節(jié)點(diǎn)的有向帶權(quán)拓?fù)鋱D

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

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

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

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

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

[5]張錦明，洪剛，文銳，等.Dijkstra最短路徑算法優(yōu)化策略[J].測繪科學(xué)，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)算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)，2012，41（2）:195-200.

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

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

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

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

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

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

[14]黃書力，胡大裟，蔣玉明.經(jīng)過指定的中間節(jié)點(diǎn)集的最短路徑算法[J].計(jì)算機(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]熊揚(yáng)宇，宋鵬，王建余，等.紫外光通信網(wǎng)節(jié)點(diǎn)設(shè)計(jì)與性能分析[J].西安工程大學(xué)學(xué)報(bào)，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—），男，四川仁壽人，碩士研究生。研究方向：信息獲取與處理、計(jì)算機(jī)網(wǎng)絡(luò)路由。