求所有最小點(diǎn)成本最短路徑算法

何建軍　王麗芳

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

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

DOIDOI：10.11907/rjdk.1431088

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）004007803

0引言

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

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

1問題描述

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

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

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

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

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

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

2算法基本思想

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

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

3算法描述

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

定理2：算法1能正確求出從源點(diǎn)到各個(gè)頂點(diǎn)的LC二元組。

證明：對(duì)放入S中的定點(diǎn)次序k進(jìn)行歸納：

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

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

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

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

4算法性能分析和實(shí)例

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

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

5結(jié)語

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

參考文獻(xiàn)參考文獻(xià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]周益民，孫世新，田 玲.一種實(shí)用的所有點(diǎn)對(duì)之間最短路徑并行算法[J].計(jì)算機(jī)應(yīng)用，2005，25（12）：29212922.

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

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

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

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

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

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

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

[12]周經(jīng)倫，吳喚群.受頂點(diǎn)數(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é)任編輯：杜能鋼）