黃書(shū)力，胡大裟，蔣玉明

四川大學(xué) 計(jì)算機(jī)（軟件）學(xué)院，成都 610065

1 引言

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

目前以Dijkstra算法為基礎(chǔ)，針對(duì)最短路徑問(wèn)題的研究非常多。通過(guò)研究前人給出的算法的復(fù)雜性，提出一種新的時(shí)空復(fù)雜度更低的改進(jìn)算法[2-6]；基于某種特殊環(huán)境和條件，給出一種可行的最短路徑算法[7-12]；基于第一條最短路徑算法，擴(kuò)展到研究前N條最短路徑算法[13-14]。這些研究或者基于特定領(lǐng)域，給出特定環(huán)境下的最短路徑算法，或者是針對(duì)Dijkstra算法本身，提出時(shí)空效率更高的改進(jìn)算法，給研究最短路徑問(wèn)題提供了非常廣闊的思路。然而，在圖論中還存在著這樣一類(lèi)未被廣泛研究卻又有著重要實(shí)際研究意義的問(wèn)題：

（1）“郵遞員問(wèn)題”。郵遞員從郵局出發(fā)送完信件后回家（或回郵局），需要為他安排行駛路徑使得總的行駛距離最短。

（2）“旅行家問(wèn)題”。給旅行家設(shè)計(jì)一條旅行線路，使得他從某地出發(fā)，游玩一些事先計(jì)劃的旅游景點(diǎn)后，到達(dá)另一目的地的總行駛距離最短。

（3）公交車(chē)路線設(shè)計(jì)問(wèn)題。給公交車(chē)設(shè)計(jì)一條線路，使得公交車(chē)從起始站出發(fā)途經(jīng)一些重要站點(diǎn)后達(dá)到終點(diǎn)站的行駛距離最短。例如，2008年北京奧運(yùn)會(huì)期間所使用的34條經(jīng)過(guò)北京市主要奧運(yùn)場(chǎng)館的奧運(yùn)公交專(zhuān)線的設(shè)計(jì)[15]。這些奧運(yùn)公交專(zhuān)線在設(shè)計(jì)上具有一個(gè)共同的特點(diǎn)，就是從公交調(diào)度起點(diǎn)站出發(fā)后途徑一些要求經(jīng)過(guò)的奧運(yùn)場(chǎng)館站后（這里忽略公交車(chē)經(jīng)過(guò)奧運(yùn)場(chǎng)館站點(diǎn)的順序）到達(dá)公交終點(diǎn)調(diào)度站。

此外，還有諸如要求經(jīng)過(guò)某些特定的中間路由器的特殊的網(wǎng)絡(luò)選路問(wèn)題等。這類(lèi)問(wèn)題均可以歸納為：

在一個(gè)圖中，需要計(jì)算出從指定的頂點(diǎn)出發(fā)，經(jīng)過(guò)一些指定的中間節(jié)點(diǎn)（這些需要經(jīng)過(guò)的中間節(jié)點(diǎn)的個(gè)數(shù)不確定），達(dá)到指定的終點(diǎn)的最短距離和經(jīng)過(guò)的路徑。

對(duì)于此類(lèi)問(wèn)題，直接使用Dijkstra算法就無(wú)法完成了。為此，本文以Dijkstra算法為基礎(chǔ)，基于貪心理論[16-17]，以無(wú)向無(wú)權(quán)圖為例提出了一個(gè)解決此類(lèi)問(wèn)題的方法，進(jìn)行了詳細(xì)闡述，并給出了算法關(guān)鍵部分的偽代碼描述。有向圖和帶權(quán)圖的算法完全類(lèi)似，在本文結(jié)尾均做了簡(jiǎn)述。

2 問(wèn)題描述

如圖1所示，假設(shè)起點(diǎn)Vbegin為V1，用數(shù)字1表示；需要通過(guò)的中間節(jié)點(diǎn)為V3，V4，分別用數(shù)字3，4表示；終點(diǎn)Vend為V2，用數(shù)字2表示。

圖1 示例圖

如果需要求出從節(jié)點(diǎn)1到節(jié)點(diǎn)2之間的最短路徑，用Dijkstra算法可以求出路徑為1-＞2，但是如果要求必須經(jīng)過(guò)中間節(jié)點(diǎn)3，則路徑應(yīng)為1-＞3-＞2。

2.1 概念定義

相關(guān)節(jié)點(diǎn)：起點(diǎn)，終點(diǎn)，目標(biāo)路徑必須要經(jīng)過(guò)的指定的中間節(jié)點(diǎn)均為相關(guān)節(jié)點(diǎn)。

自由節(jié)點(diǎn)：網(wǎng)絡(luò)圖中，除了相關(guān)節(jié)點(diǎn)之外的其他節(jié)點(diǎn)。

全局備選最短路徑：由各段局部最短路徑所依次連接起來(lái)得到的全局最短路徑的一個(gè)備選方案。

全局最短路徑：全局備選最短路徑集合中距離最短的路徑。

2.2 問(wèn)題定義

在一個(gè)無(wú)向無(wú)權(quán)圖（記為Gold(V，E)）中，給定一個(gè)任意的起點(diǎn)（記為Vbegin），一些指定的中間節(jié)點(diǎn)（將這些指定的中間節(jié)點(diǎn)的集合記為Smid），和一個(gè)任意終點(diǎn)（記為Vend）。要求尋找一條從起點(diǎn)Vbegin出發(fā)，經(jīng)過(guò)所有指定的中間節(jié)點(diǎn)，到達(dá)終點(diǎn)Vend的距離最短的路徑。除此之外，這條最短路徑?jīng)]有任意額外條件。也就是說(shuō)，這條路徑可能會(huì)經(jīng)過(guò)網(wǎng)絡(luò)中的除了起點(diǎn)、終點(diǎn)和指定的中間節(jié)點(diǎn)之外的其他節(jié)點(diǎn)（即自由節(jié)點(diǎn)），同時(shí)，這條路徑中某些節(jié)點(diǎn)可能會(huì)出現(xiàn)多次，路徑中也可能存在回路。

3 經(jīng)過(guò)指定的中間節(jié)點(diǎn)集的最短路徑算法

貪心算法，是一種通過(guò)分級(jí)處理某些最優(yōu)解問(wèn)題的方法。貪心算法，在求解過(guò)程的每一步中都采取在當(dāng)前狀態(tài)下看來(lái)是最好或最優(yōu)的選擇，從而希望最終的結(jié)果是最好或最優(yōu)的。如果一個(gè)復(fù)雜的問(wèn)題能夠分解成幾個(gè)子問(wèn)題來(lái)解決，并且子問(wèn)題的最優(yōu)解能遞推到最終問(wèn)題的最優(yōu)解，簡(jiǎn)言之，如果局部最優(yōu)解能最終推導(dǎo)出全局最優(yōu)解，那么貪心算法在解決這類(lèi)問(wèn)題時(shí)將非常有效。

貪心算法求解問(wèn)題的基本步驟：

（1）把原問(wèn)題分解成若干個(gè)易于求解的簡(jiǎn)化的子問(wèn)題。

（2）對(duì)每一子問(wèn)題分別求解，得到所有子問(wèn)題的局部最優(yōu)解。

（3）通過(guò)對(duì)全部子問(wèn)題的某個(gè)局部最優(yōu)解進(jìn)行分析、聚合等處理，生成原問(wèn)題的一個(gè)解。

（4）從上一步所求出的原問(wèn)題的解集或某個(gè)初始解出發(fā)，通過(guò)篩選、迭代等手段求出原問(wèn)題的解（全局最優(yōu)解）。

Dijkstra算法的基本思路是先將與起點(diǎn)有邊直接相連的節(jié)點(diǎn)到起點(diǎn)的距離記為對(duì)應(yīng)的邊的權(quán)重值，將與起點(diǎn)無(wú)邊直接相連的節(jié)點(diǎn)到起點(diǎn)的距離記為無(wú)窮大。然后以起點(diǎn)為中心向外層層擴(kuò)展，計(jì)算所有節(jié)點(diǎn)到起點(diǎn)的最短距離。每次新擴(kuò)展到一個(gè)距離最短的點(diǎn)后，更新與它有邊直接相鄰的節(jié)點(diǎn)到起點(diǎn)的最短距離。當(dāng)所有點(diǎn)都擴(kuò)展進(jìn)來(lái)后，所有節(jié)點(diǎn)到起點(diǎn)的最短距離將不會(huì)再被改變，因而保證了算法的正確性[1]。

Dijkstra算法求解最短路徑問(wèn)題的基本步驟如下：

（1）設(shè)立Y和N兩個(gè)集合，Y用于保存所有等待訪問(wèn)的節(jié)點(diǎn)，N記錄所有已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。

（2）訪問(wèn)網(wǎng)絡(luò)節(jié)點(diǎn)中距離起始節(jié)點(diǎn)最近且沒(méi)有被訪問(wèn)過(guò)的節(jié)點(diǎn)，把這個(gè)節(jié)點(diǎn)放入Y中等待訪問(wèn)。

（3）從Y中找出距離起點(diǎn)最近的節(jié)點(diǎn)，放入N中，更新與這個(gè)節(jié)點(diǎn)有邊直接相連的相鄰節(jié)點(diǎn)到起始節(jié)點(diǎn)的最短距離，同時(shí)把這些相鄰節(jié)點(diǎn)加入Y中。

（4）重復(fù)步驟（2）和（3），直到Y(jié)集合為空，N集合為網(wǎng)絡(luò)中所有節(jié)點(diǎn)為止。

Dijkstra算法的基本思想和求解步驟決定了Dijkstra算法只能解決最基本的在起點(diǎn)和終點(diǎn)之間求最短路徑的問(wèn)題，無(wú)法解決添加了其他限制條件的，如本文中所探討的這類(lèi)要求經(jīng)過(guò)指定中間節(jié)點(diǎn)集的最短路徑問(wèn)題。

本文基于貪心算法，將原問(wèn)題分解成幾個(gè)易于用Dijkstra算法求解的子問(wèn)題，先對(duì)各個(gè)子問(wèn)題逐一求局部最優(yōu)解，再在此基礎(chǔ)上求全局最優(yōu)解。具體說(shuō)來(lái)，就是先將預(yù)處理后的網(wǎng)絡(luò)拓?fù)鋱D中的所有節(jié)點(diǎn)分為三個(gè)子集合，分別為包含起點(diǎn)的起點(diǎn)集，包含全部的需要經(jīng)過(guò)的中間節(jié)點(diǎn)的中間節(jié)點(diǎn)集，包含終點(diǎn)的終點(diǎn)集。通過(guò)Dijkstra算法依次求起點(diǎn)集到中間節(jié)點(diǎn)集之間的局部最短路徑，連通中間節(jié)點(diǎn)集中所有節(jié)點(diǎn)的局部最短路徑，中間節(jié)點(diǎn)集到終點(diǎn)集之間的局部最短路徑，以此求出一條從起點(diǎn)出發(fā)經(jīng)過(guò)指定的所有中間節(jié)點(diǎn)后到達(dá)終點(diǎn)的待選全局最短路徑。通過(guò)對(duì)有限的待選全局最短路徑進(jìn)行篩選，選出其中距離最短的路徑，即為滿足要求的全局最短路徑。

3.1 預(yù)處理

3.1.1 點(diǎn)和邊的數(shù)據(jù)提取

從文件中讀取節(jié)點(diǎn)和邊的數(shù)據(jù)并以鄰接矩陣形式存儲(chǔ)，同時(shí)統(tǒng)計(jì)出節(jié)點(diǎn)個(gè)數(shù)和邊的條數(shù)。

如圖2，每一行的兩個(gè)數(shù)表示著兩個(gè)節(jié)點(diǎn)之間有邊聯(lián)通。如果是帶權(quán)圖，則在后面再加一列，顯示權(quán)重即可。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)的存儲(chǔ)格式示例

如圖3，鄰接矩陣中的元素只有1和max兩種，1表示直接有邊相連，max表示無(wú)邊直接相連。max為一個(gè)事先定義的足夠大的數(shù)字。

圖3 示例圖的鄰接矩陣表示

3.1.2 剪枝

剪枝，就是從原網(wǎng)絡(luò)圖中刪去目標(biāo)路徑肯定不會(huì)經(jīng)過(guò)的節(jié)點(diǎn)。具體方法為，從起點(diǎn)Vbegin出發(fā)，深度優(yōu)先遍歷該圖，那些沒(méi)有遍歷到的節(jié)點(diǎn)肯定不會(huì)出現(xiàn)在目標(biāo)路徑上，就可以將它們從原網(wǎng)絡(luò)圖中“剪”掉。從而生成新的網(wǎng)絡(luò)圖G(V，E)，替換原來(lái)的網(wǎng)絡(luò)圖Gold(V，E)。

剪枝的目的是在不影響求目標(biāo)路徑的情況下，通過(guò)減少網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)，來(lái)大幅提高算法的時(shí)空效率。

下面給出從任意起點(diǎn)出發(fā)，經(jīng)過(guò)指定的n個(gè)中間節(jié)點(diǎn)(n≥0)，到達(dá)指定的任意終點(diǎn)的最短路徑算法。

3.2 算法描述

（1）假設(shè)需要經(jīng)過(guò)的指定中間節(jié)點(diǎn)個(gè)數(shù)為n，先判斷這n個(gè)節(jié)點(diǎn)之間的連通情況，若有任意倆節(jié)點(diǎn)不連通，則滿足條件的路徑不存在；反之，進(jìn)入下一步。

判斷是否連通的方法：在這n個(gè)節(jié)點(diǎn)中，任選一個(gè)為根節(jié)點(diǎn)，深度優(yōu)先遍歷該圖，若其他的n-1個(gè)所有節(jié)點(diǎn)都遍歷到了，則是連通的；反之，則為未連通的。

（2）對(duì)這n個(gè)中間節(jié)點(diǎn)做全排列，生成一個(gè)中間節(jié)點(diǎn)序列。全排列的起點(diǎn)記為V1，終點(diǎn)記為Vn。計(jì)算V1和Vn之間的最短距離和路徑。具體方法，見(jiàn)“求中間節(jié)點(diǎn)之間的距離和路徑的方法”。

（3）求目標(biāo)源點(diǎn)到V1的局部最短路徑，即為單源點(diǎn)最短路徑，直接使用迪杰斯特拉算法即可。若目標(biāo)源點(diǎn)和V1之間的路徑經(jīng)過(guò)了自由節(jié)點(diǎn)，則將經(jīng)過(guò)的自由節(jié)點(diǎn)按序保存到該局部路徑中。

（4）求V1到Vn的經(jīng)過(guò)所有中間節(jié)點(diǎn)的局部最短路徑，（2）中已求出。

（5）求Vn到目標(biāo)終點(diǎn)的局部最短路徑，即為單源點(diǎn)最短路徑，直接使用迪杰斯特拉算法即可。若Vn和目標(biāo)終點(diǎn)之間的路徑經(jīng)過(guò)了自由節(jié)點(diǎn)，則將經(jīng)過(guò)的自由節(jié)點(diǎn)按序保存到該局部路徑中。

（6）將以上3條路徑依序連接起來(lái)即得經(jīng)過(guò)Smid中所有節(jié)點(diǎn)的（待選）全程最短路徑。將以上3條路徑的距離相加即得該條待選全程最短路徑的距離。

（7）搜索（6）中求出的路徑，其中距離最小的即為待求的全程最短距離，對(duì)應(yīng)的路徑就是待求的最短路徑。

求中間節(jié)點(diǎn)之間的距離和路徑的方法：

對(duì)于一個(gè)中間節(jié)點(diǎn)序列，若任意倆相鄰節(jié)點(diǎn)有邊直接相連，則它們之間的距離為1（在帶權(quán)圖中，該距離為對(duì)應(yīng)邊的權(quán)重值）；反之，使用Dijkstra算法求出它們之間的最短路徑和距離。若它們之間的路徑經(jīng)過(guò)了自由節(jié)點(diǎn)，則應(yīng)將自由節(jié)點(diǎn)保存到該路徑中。將所有相鄰節(jié)點(diǎn)間的距離相加即得V1和Vn之間的最短距離；將所有相鄰節(jié)點(diǎn)間的路徑（中間可能會(huì)經(jīng)過(guò)一些自由節(jié)點(diǎn)）相連即得V1和Vn之間的最短路徑。

算法整體流程如圖4。其中，算法描述部分及流程圖中，Dijkstra(V1，V2)為利用Dijkstra算法求解從源點(diǎn)V1到V2的最短路徑的方法，見(jiàn)文獻(xiàn)[1]。相關(guān)的偽代碼及各種語(yǔ)言編寫(xiě)的程序目前都有現(xiàn)成的，在此不作綴述。

3.3 算法演示

下面以圖1所示的拓?fù)浣Y(jié)構(gòu)圖為例，演示一次該算法。

步驟1對(duì)于中間節(jié)點(diǎn)集，以3為起點(diǎn)，深度優(yōu)先遍歷該圖，能遍歷到頂點(diǎn)4，該圖是連通的。

步驟2利用中間節(jié)點(diǎn)集中的所有元素，組成全排列，形成中間節(jié)點(diǎn)序列集：3-＞4，4-＞3。

步驟3利用“求中間節(jié)點(diǎn)之間的距離和路徑的方法”，對(duì)于步驟2所得的每一個(gè)序列，求出連通中間節(jié)點(diǎn)集的局部最短距離，及對(duì)應(yīng)的局部最短路徑：

路徑1：3-＞1-＞4，距離2（距離相路徑同的路徑其實(shí)還有3-＞2-＞4，但是算法只求出一條最短路徑）。

路徑2：4-＞1-＞3，距離2（距離相同的路徑其實(shí)還有4-＞2-＞3，但是算法只求出一條最短路徑）。

分別用包含了自由節(jié)點(diǎn)的路徑1、路徑2，更新步驟2中的序列3-＞4，4-＞3。

步驟4依次對(duì)步驟3中求出的每一個(gè)中間序列的“起點(diǎn)”，求出起點(diǎn)Vbegin1到它們之間的局部最短距離。

序列1：以3為“起點(diǎn)”：Dijkstra（1，3）。

序列2：以4為“起點(diǎn)”：Dijkstra（1，4）。

步驟5依次對(duì)步驟3中求出的每一個(gè)中間序列的“終點(diǎn)”，求出它們到Vend2之間的局部最短距離。

序列1：以4為“終點(diǎn)”：Dijkstra（4，2）。

序列2：以3為“終點(diǎn)”：Dijkstra（3，2）。

步驟6將步驟4，步驟3，步驟5求出的三段路徑連接起來(lái)即得經(jīng)過(guò)中間節(jié)點(diǎn)集的“全程最短路徑”。

序列1：1-＞3-＞1-＞4-＞2。

序列2：1-＞4-＞1-＞3-＞2。

步驟7對(duì)于步驟6中所求出的每一條局部的“全程最短路徑”，求出距離最小的路徑，1-＞3-＞1-＞4-＞2 就是滿足條件的全程最短路徑，對(duì)應(yīng)的距離是4。距離相同的路徑其實(shí)還有 1-＞4-＞1-＞3-＞2，但是算法只求出一條最短路徑。如需求出最短距離相同的所有路徑，只需將算法偽代碼第27～32行略作修改即可。

3.4 算法分析

記n，m分別為總節(jié)點(diǎn)和必須經(jīng)過(guò)的中間節(jié)點(diǎn)的個(gè)數(shù)。由于Dijkstra算法的時(shí)間復(fù)雜度為O(n2)（n為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)），與邊數(shù)無(wú)關(guān)，特別適用于稠密圖。本算法以Dijkstra算法為基礎(chǔ)，算法的時(shí)間復(fù)雜度與頂點(diǎn)個(gè)數(shù)和中間節(jié)點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)，也適用于稠密圖。

理論上，該算法的時(shí)間復(fù)雜度為O(n2×m!)。從中不難看出，算法的時(shí)間復(fù)雜度對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)不敏感，可以適用于大規(guī)模網(wǎng)絡(luò)，而對(duì)于需要經(jīng)過(guò)的中間節(jié)點(diǎn)個(gè)數(shù)卻非常敏感，不太適用于中間節(jié)點(diǎn)個(gè)數(shù)太多的情況。

3.5 實(shí)驗(yàn)仿真

實(shí)驗(yàn)環(huán)境為：windows7系統(tǒng)，2.2GHz i3-2330CPU，4 GB內(nèi)存，編程語(yǔ)言是C++，譯環(huán)境為VS2010。不失一般性，下面以2013屆“中興捧月”杯程序設(shè)計(jì)大賽復(fù)賽試題2[18]中提供的數(shù)據(jù)進(jìn)行測(cè)試。

2013屆“中興捧月”杯程序設(shè)計(jì)大賽復(fù)賽試題2題干部分：在一個(gè)可以支持至少上千個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)渲?，邊是有向無(wú)權(quán)的，兩點(diǎn)之間最多有一條邊，給出源點(diǎn)和終點(diǎn)兩個(gè)點(diǎn)，需要找出滿足條件的最短路徑：這條路徑必須經(jīng)過(guò)一些給定中間節(jié)點(diǎn)（節(jié)點(diǎn)個(gè)數(shù)不超過(guò)10個(gè)）[18]。

圖4 算法流程圖

3.5.1 實(shí)驗(yàn)1：追蹤程序的求解過(guò)程，驗(yàn)證實(shí)驗(yàn)結(jié)果的正確性

為了便于追蹤、觀察程序執(zhí)行的過(guò)程和直觀驗(yàn)證最終結(jié)果的正確性，本實(shí)驗(yàn)從文獻(xiàn)[18]所提供的數(shù)據(jù)中，選取具有50個(gè)節(jié)點(diǎn)的某稀疏網(wǎng)絡(luò)進(jìn)行測(cè)試，詳細(xì)說(shuō)明程序的求解過(guò)程和結(jié)果。

網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)如圖5。

圖5 測(cè)試一使用的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)

上述網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)所形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖6。

圖6 測(cè)試1使用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

為便于完整展示程序的執(zhí)行過(guò)程，這里選取起點(diǎn)、終點(diǎn)和必須經(jīng)過(guò)的中間節(jié)點(diǎn)時(shí)，需要確保滿足條件的路徑是存在的。同時(shí)，為了使中間結(jié)果序列不至太長(zhǎng)而影響到直觀驗(yàn)證結(jié)果的正確性，這里選取起點(diǎn)20，終點(diǎn)32，需要經(jīng)過(guò)的中間節(jié)點(diǎn)為15，16，31來(lái)進(jìn)行實(shí)驗(yàn)展示。

關(guān)鍵的求解步驟及部分中間結(jié)果如表1。

通過(guò)觀察該實(shí)驗(yàn)所選擇的網(wǎng)絡(luò)圖的拓?fù)浣Y(jié)構(gòu)，不難發(fā)現(xiàn)實(shí)驗(yàn)結(jié)果的正確性。另外，通過(guò)在幾十組不同拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)數(shù)的網(wǎng)絡(luò)中隨機(jī)選取10個(gè)以內(nèi)數(shù)量不等（中間節(jié)點(diǎn)個(gè)數(shù)選取10個(gè)以內(nèi)的原因見(jiàn)實(shí)驗(yàn)2）的中間節(jié)點(diǎn)進(jìn)行測(cè)試（無(wú)論滿足條件的路徑是否存在），通過(guò)直觀驗(yàn)證，證明了該算法在計(jì)算滿足條件的最短路徑和距離的準(zhǔn)確率達(dá)到了100%。

表1 實(shí)驗(yàn)1中程序執(zhí)行關(guān)鍵步驟及結(jié)果

3.5.2 實(shí)驗(yàn)2：探索該算法在實(shí)際應(yīng)用中面對(duì)不同網(wǎng)絡(luò)環(huán)境時(shí)的時(shí)間效率

由于難以有效地對(duì)程序執(zhí)行的空間效率進(jìn)行監(jiān)測(cè)，下面僅通過(guò)在程序中設(shè)置計(jì)時(shí)器記錄程序的執(zhí)行時(shí)間來(lái)粗略探索算法的時(shí)間效率。分別通過(guò)在50個(gè)，500個(gè)和5 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中的多組數(shù)據(jù)測(cè)試，求算術(shù)平均后，得出數(shù)據(jù)如表2～4。因?yàn)橹虚g節(jié)點(diǎn)個(gè)數(shù)超過(guò)10時(shí)，程序執(zhí)行時(shí)間較長(zhǎng)。因此，在表2～4中，中間節(jié)點(diǎn)的個(gè)數(shù)分別取值為1，5，10。

表2 程序在50個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中執(zhí)行的時(shí)間表

表3 程序在500個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中執(zhí)行的時(shí)間表

表4 程序在5 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中執(zhí)行時(shí)間表

由此可見(jiàn)，即使面臨龐大的網(wǎng)絡(luò)圖，只要需要經(jīng)過(guò)的中間節(jié)點(diǎn)數(shù)不太多，程序的執(zhí)行時(shí)間都非?？捎^。本算法具有很好實(shí)際應(yīng)用前景。

但是，當(dāng)中間節(jié)點(diǎn)個(gè)數(shù)大于10時(shí)，程序的執(zhí)行時(shí)間較長(zhǎng)。同時(shí)，由于網(wǎng)絡(luò)的稠密稀疏程度存在差異，中間節(jié)點(diǎn)集在網(wǎng)絡(luò)中的分布情況存在差異，編寫(xiě)程序的語(yǔ)言和程序的編寫(xiě)邏輯存在差異，用于編程的計(jì)算機(jī)性能存在差異等，僅僅依靠節(jié)點(diǎn)個(gè)數(shù)測(cè)試出來(lái)的程序的執(zhí)行時(shí)間僅能作為參考，無(wú)法準(zhǔn)確預(yù)測(cè)算法在不同網(wǎng)絡(luò)拓?fù)鋱D中的實(shí)際使用效果。另外，從時(shí)間復(fù)雜度公式和本算法編制的程序執(zhí)行結(jié)果都可以看出，隨著中間節(jié)點(diǎn)個(gè)數(shù)增大，程序執(zhí)行的時(shí)間增加非常明顯。

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

實(shí)際上，無(wú)論是“郵遞員”、“旅行家問(wèn)題”還是公交車(chē)專(zhuān)線設(shè)計(jì)和網(wǎng)絡(luò)選路問(wèn)題，還是其他類(lèi)似問(wèn)題，不同節(jié)點(diǎn)之間的距離或者網(wǎng)絡(luò)時(shí)延都是不一樣的，是帶權(quán)的，因此帶權(quán)圖更適合實(shí)際生產(chǎn)生活實(shí)際。針對(duì)帶權(quán)圖的算法跟無(wú)權(quán)圖十分相似，對(duì)于上面提出的算法，稍作修改即可用于帶權(quán)圖。

（1）鄰接矩陣的元素不再只是1和max了，而是實(shí)際的權(quán)重（邊的長(zhǎng)度，網(wǎng)絡(luò)的時(shí)延等）。

（2）算法描述部分“求中間節(jié)點(diǎn)之間的距離和路徑的方法”中偽代碼的第五行，若序列中的倆相鄰節(jié)點(diǎn)是有邊直接相連的，則距離為鄰接矩陣中對(duì)應(yīng)行列的值。

針對(duì)有向圖，算法跟無(wú)向圖完全相同，無(wú)需更改即可直接使用。

在中間節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，該算法時(shí)間復(fù)雜度極低。該算法在需要經(jīng)過(guò)的中間節(jié)點(diǎn)個(gè)數(shù)較少的最短路徑問(wèn)題中，例如，郵遞員送信路線選擇，針對(duì)重要線路和站點(diǎn)的公交路線設(shè)計(jì)，以及旅行家問(wèn)題等許多基于圖的優(yōu)化問(wèn)題中，都有著廣泛的應(yīng)用前景。為在經(jīng)過(guò)指定節(jié)點(diǎn)集的較大規(guī)模稠密網(wǎng)絡(luò)中求最短路徑提供了新的思路。盡管如此，如何改進(jìn)該算法，以便在海量網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和大量中間節(jié)點(diǎn)集的情況下提高算法時(shí)空效率，還需要進(jìn)一步的研究和探索。

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

[2]Sang Yongsheng，Yi Zhang.A modified pulse coupled neural network for shortest path computation[J].Journal of Computational Information Systems，2010，6（9）：3095-3102.

[3]Goldberg A V，Kaplan H，Werneck R F.Reach for A*：efficient point-to-point shortest path algorithms[C]//ALENEX，2006，6（2）：129-143.

[4]Orlin J B，Madduri K，Subramani K，et al.A faster algorithm for the single source shortest path problem with few distinct positive lengths[J].Journal of Discrete Algorithms，2010，8（2）：189-198.

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

[6]王智廣，王興會(huì)，李妍.一種基于Dijkstra最短路徑算法的改進(jìn)算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)：自然科學(xué)漢文版，2012，41（2）：195-200.

[7]徐慶征，柯熙政.求解最短路徑的遺傳算法中若干問(wèn)題的討論[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（6）：1507-1509.

[8]Chan T M.More algorithms for all-pairs shortest paths in weighted graphs[J].SIAM Journal on Computing，2010，39（5）：2075-2089.

[9]林瀾，閆春鋼，蔣昌俊，等.動(dòng)態(tài)網(wǎng)絡(luò)最短路問(wèn)題的復(fù)雜性與近似算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（4）：608-614.

[10]唐晉韜，王挺，王戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報(bào)，2011，22（10）：2279-2290.

[11]王衛(wèi)強(qiáng)，孫強(qiáng).求圖中受頂點(diǎn)數(shù)限制的所有最短路徑的算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（7）：1754-1757.

[12]葉金平，朱征宇，王麗娜，等.智能交通中的高效多準(zhǔn)最短路徑混合算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3301-3304.

[13]柴登峰，張登榮.前N條最短路徑問(wèn)題的算法及應(yīng)用[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2002，36（5）：531-534.

[14]王峰，游志勝，曼麗春，等.Dijkstra及基于Dijkstra的前N條最短路徑算法在智能交通系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2006，23（9）：203-205.

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

[16]Koutsoupias E，Papadimitriou C H.On the greedy algorithm for satisfiability[J].Information Processing Letters，1992，43（1）：53-55.

[17]Martello S，Toth P.Knapsack problems[M].New York：Wiley，1990.

[18]“中興捧月”杯程序設(shè)計(jì)大賽復(fù)賽試題[EB/OL].[2013-12-10].http：//company.dajie.com/zte/competition?r=13844132497.