改進(jìn)的最短路徑矩陣迭代標(biāo)號(hào)法

薛瑞，黃式東，潘虹

（1.信陽(yáng)師范學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院，信陽(yáng)　464000；2.信陽(yáng)師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，信陽(yáng)　464000）

改進(jìn)的最短路徑矩陣迭代標(biāo)號(hào)法

薛瑞1，黃式東1，潘虹2

（1.信陽(yáng)師范學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院，信陽(yáng)464000；2.信陽(yáng)師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，信陽(yáng)464000）

0　引言

最短路徑（Shortest Paths，SP）是一種典型的網(wǎng)絡(luò)優(yōu)化模型，是解決兩結(jié)點(diǎn)之間的最小代價(jià)問(wèn)題。許多優(yōu)化問(wèn)題，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等，都可轉(zhuǎn)化為網(wǎng)絡(luò)最短路徑問(wèn)題。算法具體的形式包括：確定起點(diǎn)的最短路徑問(wèn)題、確定終點(diǎn)的最短路徑問(wèn)題、全局最短路徑問(wèn)題等。其次還有一些關(guān)于最短路徑算法的變形算法相繼被提出：多目標(biāo)最短路徑算法［1］、K-最短路徑算法［2］、時(shí)序最短路徑算法［3］等。

用于解決最短路徑問(wèn)題的算法被稱做 “最短路徑算法”。到目前為止，解決最短路徑常用的算法有Dijkstra算法［4］和Floyd算法［5］，以及啟發(fā)式A*算法［6］等。在這些算法中，Dijkstra算法是典型的單源最短路徑算法。

1　Dijkstra算法概述與分析

Dijkstra算法使用了廣度優(yōu)先搜索解決非負(fù)權(quán)有向圖的單源最短路徑問(wèn)題。所謂單源最短路徑問(wèn)題是指：已知圖G=（V，E），找出從源結(jié)點(diǎn)v1到圖中其他各結(jié)點(diǎn)的最短路徑。Dijkstra算法的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。對(duì)Dijkstra算法的改進(jìn)是近年來(lái)國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)。例如文獻(xiàn)［7］提出了基于改進(jìn)蟻群算法的最短路徑問(wèn)題；文獻(xiàn) ［8，9］針對(duì)多鄰接點(diǎn)與多條最短路徑提出了改進(jìn)的Dijkstra算法算法；文獻(xiàn)［10］提出了改進(jìn)的Dijkstra算法在多目標(biāo)優(yōu)化中的應(yīng)用。文獻(xiàn)［11］利用分布式稀疏矩陣對(duì)Dijkstra算法進(jìn)行優(yōu)化。

1.1Dijkstra算法步驟

如果存在一條從源結(jié)點(diǎn)v1到vj的最短路徑（v1，…，vi，vj），vi是vj前面的一結(jié)點(diǎn)，那么（v1，…，vi）也必定是從v1到vi的最短路徑。可得從結(jié)點(diǎn)v1到達(dá)vj的最短距離dist［j］=min｛dist［j］，dist［i］+matrix［i］［j］｝［4］。假設(shè)圖G= ＜V，E＞，源結(jié)點(diǎn)為v1，P=｛v1｝，dist［j］記錄v1到vj的最短距離，path［j］記錄從v1到vj路徑上的vj前面的一個(gè)結(jié)點(diǎn)。

①?gòu)腣-P中選擇使dist［i］值最小的結(jié)點(diǎn)vi，將vi加入到P中；

②更新與vi直接相鄰結(jié)點(diǎn)vj的dist值。（dist［j］= min｛dist［j］，dist［i］+matrix［i］［j］｝）；

③直到P=V，停止。

1.2Dijkstra算法的不足之處

（1）Dijkstra算法不能解決負(fù)權(quán)值最短路徑問(wèn)題，如圖1所示：

圖1　帶負(fù)權(quán)圖G1

計(jì)算從源結(jié)點(diǎn)v1到結(jié)點(diǎn)v5的最短路徑，用Dijkstra算法得到的結(jié)果是v1-v3-v4-v5。主要原因是Dijkstra算法采用的是“標(biāo)簽算法”，而且對(duì)于標(biāo)記過(guò)的點(diǎn)不再進(jìn)行更新。當(dāng)v3做為距v1距離最短的點(diǎn)加入邊集U之后，即使負(fù)權(quán)值可以使得最短值縮短，程序也不會(huì)返回v2重新計(jì)算最短路徑。

（2）Dijkstra算法需要多次修改結(jié)點(diǎn)最短路徑的長(zhǎng)度。由于算法遍歷的結(jié)點(diǎn)多，特別是對(duì)于稠密圖，算法的效率較低。

（3）當(dāng)從開(kāi)始點(diǎn)到某個(gè)結(jié)點(diǎn)之間可能存在多條權(quán)重相同的最短路徑時(shí)，Dijkstra算法沒(méi)有涉及。Dijkstra算法默認(rèn)為最短路徑上某個(gè)結(jié)點(diǎn)只有一個(gè)前置鄰接點(diǎn)，如圖2所示，從結(jié)點(diǎn)v1到結(jié)點(diǎn)v7的最短路徑有3條，而用Dijkstra算法只能得到一條最短路徑。

圖2　帶權(quán)圖G2

為此，本文針對(duì)Dijkstra算法的以上幾點(diǎn)不足，提出了改進(jìn)的矩陣迭代標(biāo)號(hào)法，有效地解決Dijkstra算法的以上幾點(diǎn)不足之處。

2　矩陣迭代標(biāo)號(hào)法思想步驟

設(shè)簡(jiǎn)單圖G=＜V，E＞，V=｛v1，v2，…，vn｝，E=｛e1，e2，…，em｝，由于矩陣在計(jì)算機(jī)中易于存儲(chǔ)和處理，因此可利用矩陣將圖表示在計(jì)算機(jī)中。稱n階方陣A=（aij）n×n為帶權(quán)圖G的距離矩陣。其中：

2.1正圖矩陣迭代算法步驟

令dist（l）［j］表示從源結(jié)點(diǎn)v1到達(dá)結(jié)點(diǎn)vj長(zhǎng)度≤l的的最短距離。由于最短路徑是單向無(wú)回路的，所以最短路徑最大長(zhǎng)度為n-1。為求結(jié)點(diǎn)v1到結(jié)點(diǎn)vj的最短距離，初始時(shí)v1到vj長(zhǎng)度為1的最短距離為 a1 j，接著計(jì)算v1到vj長(zhǎng)度為≤2的最短路徑為，以此類(lèi)推。若n個(gè)點(diǎn)分別以1，2，…，n為編號(hào)，迭代過(guò)程如下：

①取dist（1）［j］為v1到vj長(zhǎng)度為1的最短路徑，則：

③當(dāng)dist（l）［j］=dist（l-1）［j］，迭代結(jié)束，輸出dist（l）［j］=dist ［j］。

定理1：設(shè)圖G=＜V，E＞，V=｛v1，v2，…，vn｝，E=｛e1，e2，…，em｝且圖G為簡(jiǎn)單帶正權(quán)圖，則迭代序列單調(diào)遞減收斂于dist［j］，即dist（l）［j］≤dist（l-1）［j］，1≤l≤n-1。

因?yàn)閱卧醋疃搪窂绞菃蜗驘o(wú)回路的，故當(dāng)dist（l）［j］= dist（l-1）［j］時(shí)，dist（l）［j］=dist［j］。

定理2：對(duì)一個(gè)具有n個(gè)結(jié)點(diǎn)m條邊的有向圖G，若dist（l-1）［j］=dist（l-2）［j］，即第l-1次的迭代結(jié)果沒(méi)有變化（1≤l≤n-1），則迭代過(guò)程可提前結(jié)束。

當(dāng)圖為正權(quán)簡(jiǎn)單圖時(shí)，迭代序列（3）可以快捷地找出最短徑，但是如果存在從源點(diǎn)可達(dá)的負(fù)回路，則迭代序列因不能收斂而不能求出最短路徑。如圖3所示：

圖3　帶負(fù)權(quán)圖G3

取v1為源結(jié)點(diǎn)，利用迭代序列（3）的迭代結(jié)果為：

dist（2）［j］=（0，1，-1，2，0）T，dist（3）［j］=（0，-3，-1，-3，-1）T，dist（4）［j］=（0，-3，-5，-4，-6）T，…，原因是存在負(fù)權(quán)值回路造成序列不收斂，不能求出最短路徑。

若圖中出現(xiàn)權(quán)值為負(fù)的邊，如何避免負(fù)權(quán)值回路是算法的關(guān)鍵。目前國(guó)內(nèi)外關(guān)于這方面的研究結(jié)果非常少，美國(guó)數(shù)學(xué)家Richard Bellman和Lester Ford先后提出一種動(dòng)態(tài)規(guī)劃模式算法Bellman-Ford算法［12］，如果存在dist［u］+w（u，v）＜dist［v］的邊，則圖中存在負(fù)權(quán)值回路，程序返回false。Bellman-Ford算法的限制條件是圖中不能有負(fù)權(quán)值的回路，而且公式dist［u］+w（u，v）＜dist［v］是判斷回路的必要條件而非充分條件，從而會(huì)造成最短路徑漏失。

2.2負(fù)權(quán)圖矩陣迭代標(biāo)號(hào)法思想步驟

對(duì)一個(gè)具有n個(gè)結(jié)點(diǎn)m條邊的簡(jiǎn)單負(fù)權(quán)圖G，首先對(duì)n個(gè)點(diǎn)分別編號(hào)為1，2，…，n，規(guī)定源結(jié)點(diǎn)編號(hào)為1。構(gòu)造距離矩陣A=（aij）n×n，令dist（l）［j］表示從源結(jié)點(diǎn)1到達(dá)結(jié)點(diǎn)j的長(zhǎng)度≤l的的最短距離。設(shè)Aj表示從源結(jié)點(diǎn)1到點(diǎn)j的最短路徑。U［j］表示從1到j(luò)路徑上結(jié)點(diǎn)的集合。當(dāng)j=1時(shí)，U［1］=｛v1｝；dist（1）［1］=0；當(dāng)j≠1時(shí)，U［j］=｛v1，vj｝，dist（1）［j］=a1j，j=2，3，…，n。utemp［i］表示臨時(shí)最短路徑上節(jié)點(diǎn)的集合，utemp［j］的初始值等于U［j］，j=1，2，3，…，n。

①路徑長(zhǎng)度l=2，并且路徑長(zhǎng)度l＜=n-1；

②現(xiàn)求從v1到vj路徑長(zhǎng)度為l的最短路徑，對(duì)于頂點(diǎn)Vj，有j=2，j＜=n；

③對(duì)于任意的aij，如果vj不屬于U［i］，b［i］=dist（l-l）［i］+aij，utemp［i］=U［i］∪｛vj｝；否則b［i］=無(wú)窮大，utemp［i］=U［i］；

④求b［i］數(shù)組的最小值min｛b［i］｝；

如果min｛b［i］｝＜dist（l-1）［j］，那么dist（l）［j］=min｛b［i］｝，U［j］=utemp［i］；

否則dist（l）［j］=dist（l-1）［j］，U［j］=U［j］；j=j+1，轉(zhuǎn)到②；

⑤如果l=n-1，迭代結(jié)束，否則l=l+1，轉(zhuǎn)到②。

2.3仿真實(shí)驗(yàn)分析

仍以圖3中負(fù)權(quán)圖G3為例，v1，v2，v3，v4，v5分別編號(hào)為1，2，…，5，用新算法進(jìn)行迭代，源結(jié)點(diǎn)v1到其余結(jié)點(diǎn)的最短路徑及最短路徑權(quán)值如表1所示：

表1　新算法的實(shí)驗(yàn)結(jié)果

dist（3）［j］=dist（2）［j］，迭代提前結(jié)束。

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

由于改進(jìn)算法不存在負(fù)權(quán)值回路，每次迭代最多需要n-1步，一共最多有n-1次迭代，因此時(shí)間復(fù)雜度為：

f（n）≤（n-1）·（n-1）∈O（n2）

算法的最壞時(shí)間復(fù)雜度為O（n2）。傳統(tǒng)的Dijkstra算法每次迭代總共需要不超過(guò)2（n-1）2+（n-2）步，一共可能有n-1次迭代，所以：

f（n）≤（n-1）·［2（n-1）2+（n-2）］∈O（n3）

改進(jìn)算法的時(shí)間復(fù)雜度低于Dijkstra算法，重要的是當(dāng)圖中存在負(fù)權(quán)邊或負(fù)權(quán)值回路時(shí)，改進(jìn)算法仍能得到單向無(wú)回路的最短路徑。

3　應(yīng)用實(shí)例

現(xiàn)信陽(yáng)市政府需要規(guī)劃羊山新區(qū)的建設(shè)工程系統(tǒng)，新區(qū)建設(shè)主要是由5項(xiàng)子工程構(gòu)成的：城市交通工程系統(tǒng)、城市供電工程系統(tǒng)、城市綠化工程系統(tǒng)、城市通信工程系統(tǒng)、城市給水工程系統(tǒng)。由于對(duì)一項(xiàng)工程的起始條件有著嚴(yán)格的限制，所以每項(xiàng)工程的起始時(shí)間并不是很容易確定的。分別用 v1，v2，v3，v4，v5代表以上5項(xiàng)子工程的起始時(shí)間（單位：月），工程起始的時(shí)間差由8個(gè)約束條件組成：v2-v1≥0；v5-v1≥1；v2-v5≤1；v3-v1≤5；v4-v1≤4；v3-v4≥1；v3-v5≥3；v4-v5≥3。

根據(jù)本文改進(jìn)算法知道dist［i］+aij≥dist［j］，可以轉(zhuǎn)化為dist［i］-dist［j］≥-aij，因此可以做以下轉(zhuǎn)化：若vivj≥-k，則建立一條連接xi到xj的邊，邊權(quán)為k；若vsvt≤k，先變形為vt-vs≥-k，再建立一條邊權(quán)為k的連接vt到vs的邊。構(gòu)建矩陣：

5個(gè)點(diǎn)分別編號(hào)為1，2，…，5，規(guī)定源結(jié)點(diǎn)v1=0，迭代結(jié)果為：

dist［2］=2，dist［3］=5，dist［4］=4，dist［5］=1。

源結(jié)點(diǎn)到個(gè)結(jié)點(diǎn)的最短路徑為（0，2，5，4，1），即各項(xiàng)工程開(kāi)工的最短期限。

4　結(jié)語(yǔ)

本文針對(duì)Dijkstra算法的缺點(diǎn)和不足，提出了改進(jìn)的矩陣迭代標(biāo)號(hào)算法。改進(jìn)算法不僅可以有效求解負(fù)權(quán)值最短路徑問(wèn)題，而且當(dāng)從源結(jié)點(diǎn)到終點(diǎn)之間可能存在多條權(quán)重相同的最短路徑時(shí)，改進(jìn)算法可以得到所有的最短路徑，此外改進(jìn)算法采取標(biāo)號(hào)的方法，可以有效解決圖中存在負(fù)權(quán)值回路時(shí)的最短路徑問(wèn)題。由于負(fù)權(quán)值最短路徑問(wèn)題廣泛應(yīng)用于差分約束系統(tǒng)等優(yōu)化模型中，因此，本文提出的改進(jìn)算法具有很大的應(yīng)用價(jià)值。另外，在本文的迭代算法中當(dāng)計(jì)算到dist（l）［j］時(shí)，dist（l）［1］，dist（l）［2］，…，dist（l）［j-1］都已求得，但卻被束之高閣。因新計(jì)算出來(lái)的分量要比舊分量更優(yōu)化，如何用新分量代替舊分量dist（l-1）［1］，dist（l-1）［2］，…，dist（l-1）［j-1］，從而提高算法的收斂速度，這將是后續(xù)的研究工作。

［1］Daniel D，Leonardo L，Andres L M.An exact method for the biobjective shortest path problem for the large-scale road networks［J］. European Journal of Operational Research，2015，242：788-797.

［2］Shi N.Constrained shortest path problem［J］.IEEE Transactions on Automations Science and Engineering，2010，7（1）：15-23.

［3］鄧冬梅，王冠楠，朱建等.時(shí)序最短路徑算法［J］.計(jì)算機(jī)科學(xué)，2014，41（6）：185-230.

［4］Dijkstra E W.A note on two problems in connetion with graphs［J］.Numberische Mathematik，1959，1（1）：269-271.

［5］Hougardy S.The floyed-warshall algorithm on graphs with negative cycles［J］.Information Processing Letter，2010，4：279-281.

［6］Nicosia G，Oriolo G.An approximate A*algorithm and its application on the SCS problem［J］.Theoretical Computer Science，2003，290 （3）：2021-2029.

［7］宋錦娟，白艷萍.基于改進(jìn)蟻群算法的最短路徑問(wèn)題研究及應(yīng)用［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013，43（3）：156-164.

［8］王樹(shù)西，李安渝.Dijkstra算法中的多鄰接點(diǎn)與多條最短路徑問(wèn)題［J］.計(jì)算機(jī)科學(xué)，2014，41（6）：217-224.

［9］Wang S X.The improved dijkstra's shortest path algorithm and its application［J］.Procedia Engineering，2012，（29）：1186-1190.

［10］Antonio S N，Andrea R.A dijkstra-like method computing all extreme supported nondominated solutions of the biobjective shortest path problem［J］.Computer&Operations Research，2015（57）：83-94.

［11］Tintor V，Radunovi A J.Distributed dijkstra sparse placement routing algorithm for translucent optical networks［J］.Photonic Network Communication，2009，18（1）：55-64.

［12］Bellman R E.On the routing problem［J］.Quarterly of Applied Mathematics，1958，16（1）：87-90.

Dijkstra Algorithm；Shortest Path Algorithm；Matrix Algorithm

Improved Matrix Iterative Label Algorithm for the Shortest Path Problem

XUE Rui1，HUANG Shi-dong1，PAN Hong2

（1.College of Computer and Information Technology，Xinyang Normal University，Xinyang 464000；2.College of Mathmatics and Information Science，Xinyang Normal University，Xinyang 464000）

1007-1423（2015）26-0003-05

10.3969/j.issn.1007-1423.2015.26.001

薛瑞（1979-），女，碩士，講師，研究方向?yàn)橹悄苡?jì)算、信息安全

黃式東（1987-），男，河南信陽(yáng)人，碩士，助教，研究方向?yàn)橹悄苡?jì)算

潘虹（1980-），女，山東臨沂人，碩士，講師，研究方向?yàn)榇鷶?shù)拓?fù)鋵W(xué)

2015-09-01

2015-09-10

最短路徑模型是圖論研究中的經(jīng)典問(wèn)題，針對(duì)傳統(tǒng)的Dijkstra算法的不足，提出改進(jìn)的矩陣迭代標(biāo)號(hào)法。改進(jìn)算法不僅可以有效地求解負(fù)權(quán)值最短路徑問(wèn)題，而且當(dāng)兩點(diǎn)間存在多條最短路徑時(shí)，改進(jìn)算法可以同時(shí)得到所有的最短路徑。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的時(shí)間復(fù)雜度低于傳統(tǒng)的Dijkstra算法，且算法簡(jiǎn)單、易于實(shí)現(xiàn)。

Dijkstra算法；最短路徑；矩陣算法

國(guó)家自然科學(xué)基金青年基金（No.11211400）、河南省自然科學(xué)基金研究項(xiàng)目（No.142300410393）

The shortest path model is a classical problem in graph theory，aiming at the shortage of the traditional Dijkstra algorithm，proposes a matrix iterative label algorithm.The Improved algorithm can not only effectively solve the negative weight shortest path problem，and when there are exist multiple shortest paths between two points，the improved algorithm can also get all the shortest paths.Experimental results show that，the improved algorithm has lower time complexity than the traditional Dijkstra algorithm，and the algorithm is simple and easy to implement.