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

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

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

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

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

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

傳統(tǒng)的Dijkstra算法只是針對(duì)起點(diǎn)和終點(diǎn)求解最短路徑，而不能解決從起點(diǎn)出發(fā)，經(jīng)過(guò)必經(jīng)節(jié)點(diǎn)集，到達(dá)終點(diǎn)的無(wú)重復(fù)節(jié)點(diǎn)且無(wú)回路的最短路徑問(wèn)題。為此，在有向非負(fù)權(quán)圖中，提出了Dijkstra算法和回溯法相結(jié)合的方法。對(duì)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)路徑。通過(guò)實(shí)際的算法實(shí)現(xiàn)，測(cè)試大量的有向非負(fù)權(quán)圖數(shù)據(jù)，證實(shí)了算法的有效性和正確性。

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

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

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

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

1 問(wèn)題描述

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

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

以0為起點(diǎn)，經(jīng)過(guò)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 問(wèn)題定義

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

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

文中將龐大的稀疏圖，分解成幾個(gè)易于求解的子問(wèn)題，然后再全局求解最短路徑。因此，對(duì)求解稀疏圖必經(jīng)節(jié)點(diǎn)的最短路徑問(wèn)題，可以分解為兩個(gè)過(guò)程：1）求解關(guān)鍵節(jié)點(diǎn)間的最短路徑，將龐大的有向非負(fù)權(quán)稀疏圖簡(jiǎ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)過(guò)所有必經(jīng)節(jié)點(diǎn)到達(dá)終點(diǎn)，且無(wú)重復(fù)節(jié)點(diǎn)無(wú)回路的最短路徑。

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

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

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

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

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

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

3）存儲(chǔ)關(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）將每個(gè)單點(diǎn)輔助結(jié)構(gòu)進(jìn)行初始化：a）currentID設(shè)置為該單點(diǎn)的序號(hào)；b）passed設(shè)置為false（表示未經(jīng)過(guò)）；c）weight設(shè)置為無(wú)窮大（表示不可達(dá)）；d）parent設(shè)置為-1（表示為沒(méi)有父節(jié)點(diǎn)）。

3）選定一個(gè)沒(méi)有計(jì)算過(guò)且非終點(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)過(guò)）；b）weight設(shè)置為0（表示起點(diǎn)）；c）parent設(shè)置為-1（表示為沒(méi)有父節(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)過(guò)；b）源關(guān)鍵節(jié)點(diǎn)到擴(kuò)展節(jié)點(diǎn)的權(quán)值與當(dāng)前擴(kuò)展節(jié)點(diǎn)到弧頭節(jié)點(diǎn)的權(quán)值之和newWeight小于之前對(duì)該弧頭節(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)過(guò)的、有后繼節(jié)點(diǎn)且權(quán)值最小的節(jié)點(diǎn)expandVertexTmp。若expandVertexTmp為關(guān)鍵節(jié)點(diǎn)，那么設(shè)置expandVertexTmp為經(jīng)過(guò)，即設(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相同的位置，存儲(chǔ)SourceKeyVertex到其他關(guān)鍵節(jié)點(diǎn)的路徑信息。重復(fù)步驟2，繼續(xù)選定一個(gè)未計(jì)算過(guò)且非終點(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ò)所有關(guān)鍵節(jié)點(diǎn)的最短路徑

稀疏圖轉(zhuǎn)換為關(guān)鍵節(jié)點(diǎn)間的鏈接稠密圖后，這就轉(zhuǎn)換為查找一條從起點(diǎn)出發(fā)，經(jīng)過(guò)所有的必經(jīng)節(jié)點(diǎn)，到達(dá)終點(diǎn)的最小權(quán)值路徑問(wè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)先搜索時(shí)不作為擴(kuò)展節(jié)點(diǎn)的關(guān)鍵節(jié)點(diǎn)信息存儲(chǔ)棧。

std::stack＜Assist＞ onePointAssistStack；

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

std::stack＜unsigned int＞ minWeightPath；

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

1）初始化每個(gè)單點(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ò)了所有的關(guān)鍵節(jié)點(diǎn)，新的擴(kuò)展節(jié)點(diǎn)為終點(diǎn)，并且到達(dá)終點(diǎn)的權(quán)值比之前到達(dá)的權(quán)值小。a）若滿足要求，則清空minWeightPath存儲(chǔ)結(jié)構(gòu)中的路徑信息，并存儲(chǔ)該條路徑中的所有節(jié)點(diǎn)（關(guān)鍵節(jié)點(diǎn)和自由節(jié)點(diǎn)）編號(hào)。轉(zhuǎn)到第4步驟。b）若不滿足要求，轉(zhuǎn)到第3步驟。

3）查找一個(gè)新的擴(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)過(guò)；未提前到達(dá)終點(diǎn)；到所判定的關(guān)鍵節(jié)點(diǎn)的權(quán)值未超過(guò)已有路徑的最小權(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)過(guò)，以及更新相應(yīng)的父節(jié)點(diǎn)值。并將第一個(gè)有效的關(guān)鍵節(jié)點(diǎn)作為新的擴(kuò)展節(jié)點(diǎn)，其他有效的關(guān)鍵節(jié)點(diǎn)壓入關(guān)鍵信息存儲(chǔ)棧中，重復(fù)第3步驟。b）若擴(kuò)展節(jié)點(diǎn)到其他的關(guān)鍵節(jié)都無(wú)效，轉(zhuǎn)到第4步驟。

4）判定關(guān)鍵信息存儲(chǔ)棧是否為空。a）若棧為空，結(jié)束回溯深度優(yōu)先搜索算法；b）若棧不為空，從關(guān)鍵信息存儲(chǔ)棧中彈出一個(gè)關(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)過(guò)；更新新擴(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)先搜索過(guò)程，步驟3判定節(jié)點(diǎn)的有效性保證了所求得的路徑中無(wú)重復(fù)節(jié)點(diǎn)無(wú)回路。回溯深度優(yōu)先搜索的方式保證了搜索出來(lái)的結(jié)果肯定是滿足條件且全局最優(yōu)的結(jié)果，即該條路徑是從起點(diǎn)出發(fā)，經(jīng)過(guò)所有的必經(jīng)節(jié)點(diǎn)，到達(dá)終點(diǎn)無(wú)重復(fù)節(jié)點(diǎn)無(wú)回路的最短路徑。

5 算法實(shí)例測(cè)試

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

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

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

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

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

通過(guò)Dijkstra運(yùn)算后，關(guān)鍵節(jié)點(diǎn)間的路徑如表2所示。關(guān)鍵節(jié)點(diǎn)間的權(quán)重值的稠密矩陣關(guān)系如表3所示。其中，關(guān)鍵節(jié)點(diǎn)間的簡(jiǎn)化鏈接，可能是經(jīng)過(guò)自由節(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)過(guò)自由節(jié)點(diǎn)15和18。Path中沒(méi)有自由節(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個(gè)關(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)確的找出滿足條件的最短路徑，且無(wú)重復(fù)節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

7 結(jié)束語(yǔ)

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

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

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

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

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

[5]張錦明，洪剛，文銳，等.Dijkstra最短路徑算法優(yōu)化策略[J].測(cè)繪科學(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]王智廣，王興會(huì)，李妍.一種基于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]王樹(shù)西，吳政學(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ī)劃及評(píng)價(jià)方法[J].城市交通，2008，6（3）:29-34.

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

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

[14]黃書(shū)力，胡大裟，蔣玉明.經(jīng)過(guò)指定的中間節(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稿件編號(hào)：201606224

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