何建軍　王麗芳

摘要摘要：對點帶成本的最短路徑問題進行了研究。根據(jù)點帶成本最短路徑問題特點，對Dijkstra算法進行修改后給出一個時間復(fù)雜度為O（|V|2+|E|）、空間復(fù)雜度為O（|V|+|E|）的算法，并在此基礎(chǔ)上充分利用問題的特點，給出一個時間復(fù)雜度為O（w|V|）、空間復(fù)雜度為O（|V|+|E|）、構(gòu)造所有點帶成本最短路徑的算法。

關(guān)鍵詞關(guān)鍵詞：最短路徑；點帶成本；帶權(quán)圖；最小點成本最短路徑

DOIDOI：10.11907/rjdk.1431088

中圖分類號：TP312

文獻標(biāo)識碼：A文章編號文章編號：16727800（2015）004007803

0引言

最短路徑（SP）問題一直是運籌學(xué)、計算機科學(xué)、交通運輸?shù)阮I(lǐng)域的研究熱點。很多實際問題都可以轉(zhuǎn)化為網(wǎng)絡(luò)中的最短路徑問題，如道路交通網(wǎng)絡(luò)中的出行路線選取問題、計算機網(wǎng)絡(luò)中的路由選擇問題等。針對網(wǎng)絡(luò)的最短路徑問題研究具有重要的理論和現(xiàn)實意義。早期專家學(xué)者研究的算法有Dijkstra算法[1]、Bellman算法[2]、Floyd算法等，現(xiàn)階段對最短路徑算法的研究呈現(xiàn)以下幾個特點：①并行化，如文獻[4][6]等；②將遺傳算法、神經(jīng)網(wǎng)絡(luò)、啟發(fā)式算法等引入最短路徑算法設(shè)計中，如文獻[7][9]等；③對各種約束條件下的最短路徑算法進行研究，如文獻[10][13]等；④研究最短路徑算法的各種優(yōu)化實現(xiàn)，如文獻[14]。

早期文獻[10]對點帶成本約束的最短路徑算法進行了研究，文獻[10]首先證明了點帶約束成本SP問題是一個NP完全問題，然后用動態(tài)規(guī)劃法給出一個時間復(fù)雜度為O（Cmn）的偽多項式時間算法。對最小點成本最短路徑問題，文獻[10]把主要目標(biāo)（路徑長度最短）的最優(yōu)解作為次要目標(biāo)（點成本最?。┑募s束條件進行求解，需要兩次調(diào)用Dijkstra算法求最短路徑，并且需要構(gòu)造網(wǎng)絡(luò)G′=（V，A′，L′），造成一些不必要的時間和空間開銷。本文對Dijkstra算法進行了改進，使其適合于求解最小點成本最短路問題，然后只調(diào)用一次修改后的Dijkstra算法，完成對最小點成本最短路問題的求解，在求解過程中不需要構(gòu)造新的網(wǎng)絡(luò)，本質(zhì)上是一個貪心算法。

1問題描述

定義1：圖G=（V，A，L）稱為點帶成本帶權(quán)圖，給它的每條邊（vi、vj）∈A賦一個非負(fù)參數(shù)li，j，稱作長度；給它的每一vi∈V賦一個正參數(shù)ci，稱作點成本。點帶成本帶權(quán)圖G中一個特殊點s稱為源點。

定義2：設(shè)P是點帶成本帶權(quán)圖中一條路徑，記P=v1v2…vrvr+1，定義P的長度為L（P）=l1，2+l2，3+…+lr，r+1。定義P上的點成本為C（P）=a1+a2+…+ar。

定義3：點帶約束成本的SP問題：求點帶成本帶權(quán)圖中給定的兩頂點間一條路徑P，使得P在滿足C（P）≤C的前提下，路徑長度最短.這里C是一個正有理數(shù)。

定義4：最小點成本最短路徑（MCSP）問題是從源點到其余各個頂點的所有最短路中求點成本最小的最短路徑，即求：min{C（P）：P是v1→vn的最短路徑}。定義5：設(shè)G=（V，A，L）是點帶成本帶權(quán)圖，SV且源點s∈S，任意vi∈V-S，從s到vi除了vi以外其它頂點都屬于S的路徑，稱為從s到vi的受S限制路徑。把從s到vi的受S限制的所有路徑中長度最短且在滿足長度最短的條件下，點成本最小的路徑稱為s到vi的受S限制最小點成本最短路徑。記s到vi的受S限制點成本最小最短路徑的長度和點成本構(gòu)成的二元組為（Li，Ci）i，簡稱LC二元組，其中Li為路徑長度，Ci為點成本。

定義6：（Li，Ci）i<（Lj，Cj）j，當(dāng)且僅當(dāng)Li

顯然集合{（Li，Ci）i|vi∈V-S}上的“≤”關(guān)系具有自反性、反對稱性和傳遞性。又由于任意兩個實數(shù)都可以比較大小，所以集合{（Li，Ci）i|vi∈V-S}和它上面的關(guān)系“≤”構(gòu)成一個全序關(guān)系，總有最小元存在。

2算法基本思想

設(shè)P=sv2，…，vk，…，vL是圖G的一條最小點成本最短路徑，則P′=v1v2，…，vk是圖G中從s到頂點vk的最小點成本最短路徑，否則設(shè)P''=sv′2v′3…vk是從s到vk的最小點成本最短路。把路徑P中頂點vk前面的部分用P''替換會得到一條可能比P更短或者與P長度相同、但點成本更小的路徑，這些都與P是從v1到vL的最小點成本最短路徑矛盾。這說明最小點成本最短路問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，可以使用動態(tài)規(guī)劃法或貪心法進行求解。

又由于{（Li，Ci）i|vi∈V-S}是有限全序集，最小元總是存在的，所以可以采用如下貪心策略：設(shè)置一個集合S，初始時S中僅含有源s，然后每次找到V-S中最小的（Li，Ci）i，將vi添加到S中，同時對數(shù)組（Lj，Cj）j按如下方式修改：（Lj，Cj）j=min{（Lj，Cj）j，（Lj，Cj）j+（li，j，aj）}，如果（vi，vj）∈E，這一過程直至S中包含所有V中頂點為止。同時若有（Lj，Cj）j=（Lj，Cj）j+（li，j，aj），其中（vi，vj）∈E，則vi 一定會出現(xiàn)在從s到vj的最小點成本最短路徑上。可以利用LC數(shù)組的這一特性構(gòu)造出所有點成本最小最短路徑，這是文獻[10]未給出的。

3算法描述

算法1：功能：計算LC數(shù)組。輸入：圖G的鄰接表和各個邊和點的權(quán)，源點s，圖G頂點數(shù)n。輸出：LC數(shù)組。

S={s}，（Ls，Cs）s=（0，as）；

for i：= 2 to n do（Li，Ci）i=（Ls，Cs）s+（ls，i，ai）；

for（i=1；i<=n-1；i++）；{從V-S中選取一個頂點vj，使其（Lj，Cj）j最??；將vj加入到S中；for vk∈（V-S）∩N（vk） do （Lk，Ck）k=min{（Lk，Ck）k，（lj，k，ak）} }算法2：功能：構(gòu)造出所有的最小點成本最短路徑。輸入：LC數(shù)組，圖G的鄰接表，源點s， 圖G頂點數(shù)n。輸出：所有最小點成本最短路徑。for（i=1；i<=n；i++）{對頂點vi 的所有鄰接點vj計算：if（（Li，Ci）i=（Lj，Cj）j+（li，j，aj））{把vi放入棧Q中；Depth（Q，G，LC，vj）；把vi彈出棧Q中；}}Depth（Q，G，LC，vh）{if（vh==s）{輸出s；自定向下輸出Q中頂點，但不彈棧}else{對頂點vh的所有鄰接點vj計算：if（（Lh，Ch）h=（Lj，Cj）j+（lh，j，aj）） {把vh放入棧Q中；Depth（Q，G，LC， vj）；把vh彈出棧Q中；}}}算法正確性證明：定理1：每次選擇一個頂點放入S中并執(zhí)行完更新操作后，得到新的、正確的LC二元組。證明：在算法初始化時，得到的LC數(shù)組顯然是正確的。放入S的頂點vi，除了vi的鄰接點外，其余頂點不會經(jīng)過vi。vi的鄰接點可能會經(jīng)過vi，但已經(jīng)對其LC進行了更新。所以，每次選擇一個頂點放入S中并且執(zhí)行完更新操作后，會得到新的、正確的LC二元組。

定理2：算法1能正確求出從源點到各個頂點的LC二元組。

證明：對放入S中的定點次序k進行歸納：

當(dāng)k=1時，首先放入S的源點s，（Ls，Cs）s的Ls是從s到s最短路徑長度，Cs是從s到s的長度最短的最小點權(quán)。

設(shè)當(dāng)k≤h時，前h個放入S中的頂點，其相應(yīng)的LC二元組分別是從s到該頂點的最短路徑長度，及從s到該頂點的所有最短路徑中的最小點權(quán)。

現(xiàn)在證明第h+1個放入S中的頂點vi，（Li，Ci）i的Li是從s到vi最短路徑長度，Ci是從s到vi的長度最短的最小點權(quán)。設(shè)P是從s到vi長度最短、且在長度最短的前提下點權(quán)最小的路徑。根據(jù)貪心選擇策略，P必經(jīng)過S外至少一個頂點才能到達(dá)vi，不妨將P從s出發(fā)，第一個經(jīng)過S外的頂點為vx 。結(jié)合定理1，這時必然有（Lx，Cx）x<（Li，Ci）i。這與貪心選擇策略矛盾。

算法1的正確性可以保障算法2是正確的。

4算法性能分析和實例

算法1：有一個二重循環(huán)，每重循環(huán)最多循環(huán)|V|次，在整個算法運行過程中最多訪問每條邊一次，所以其時間復(fù)雜度為O（|V|2+|E|）。設(shè)最小點成本最短路徑的數(shù)目為w，則算法2的時間復(fù)雜度為O（w|V|）。算法1的空間消耗主要在鄰接表存儲和LC數(shù)組存儲，其空間復(fù)雜度為O（|V|+|E|）。算法2的空間消耗主要在鄰接表、LC數(shù)組、棧的存儲和遞歸調(diào)用棧上，遞歸調(diào)用棧的深度最多為|V|，所以其空間復(fù)雜度為O（|V|+|E|）。

圖1為一個點帶成本帶權(quán)圖，用算法1和算法2求出從源點s到其余各個頂點的點成本最短路徑，如表1。

5結(jié)語

本文在文獻[10]的基礎(chǔ)上對點帶成本問題進行了研究，結(jié)合問題的特點給出了求所有點帶成本最短路徑算法。在點帶成本最短路徑問題中，把所有點的成本都設(shè)為1，則點帶成本路徑問題就變成了頂點數(shù)最少的路徑問題。雖然本文給出了一個求解點帶成本問題的多項式時間算法，但如果圖中定點數(shù)過多，其二階的時間消耗仍然是難以接受的。所以，下一步的研究方向是點帶權(quán)最短路徑問題的并行化算法和線性近似算法。

參考文獻參考文獻：

[1]DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerical Mathematics， 1959（1）：269271.

[2]BELLMAN R.On a routing problem[J].In Quarterly of Applied M athematics， 1958， 16（1）： 8790.

[3]DEON ，PANGCY.Shortest path algorithms：taxo no my and annotation[J].Networks，1984（14）： 275323.

[4]周益民，孫世新，田 玲.一種實用的所有點對之間最短路徑并行算法[J].計算機應(yīng)用，2005，25（12）：29212922.

[5]黃躍峰，鐘耳順.多核平臺并行單源最短路徑算法[J].計算機工程，2012，38（3）：13.

[6]盧照，師軍.并行最短路徑搜索算法的設(shè)計與實現(xiàn)[J].計算機工程與應(yīng)用，2010，46（3）：6971.

[7]鄒亮，徐建閩.基于遺傳算法的動態(tài)網(wǎng)絡(luò)中最短路徑問題算法[J].計算機應(yīng)用， 2005， 25（4）：742744.

[8]洪斌， 張紅嶺，王劍雄，等.求解多約束最短路徑的改進ACNN算法[J].河北建筑工程學(xué)院學(xué)報，2013，31（3）：109112.

[9]戴樹貴，潘蔭榮，胡幼華，等.求帶多個限制條件的單源多權(quán)最短路徑算法[J].計算機應(yīng)用與軟件，2004，21（12）：7881.

[10]李幫義，何 勇，姚恩瑜.點帶約束成本的最短路問題[J].高校應(yīng)用數(shù)學(xué)學(xué)報，2000，15（1）：9396.

[11]郝光，張殿業(yè)，馮勛省.多目標(biāo)最短路徑模型及算法，2007，42（5）：641646.

[12]周經(jīng)倫，吳喚群.受頂點數(shù)限制的最短路問題及其算法[J].系統(tǒng)工程，1996，14（5）：3744.

[13]FREDMAN M L， TARJAN R E.Fibonacci heaps and their uses in improved network optimization algorithms[J].ACM， 1987， 34（3）： 596615.

[14]CHERKASSKY B V， GOLDBERG A V， RADZIK T.Shortest path algorithms： theory and experimental evaluation[J].Mathematical Programming， 1996（73）：129174.

責(zé)任編輯（責(zé)任編輯：杜能鋼）