改进的最短路径矩阵迭代标号法

薛瑞，黄式东，潘虹

（1.信阳师范学院计算机与信息技术学院，信阳　464000；2.信阳师范学院数学与信息科学学院，信阳　464000）

改进的最短路径矩阵迭代标号法

薛瑞1，黄式东1，潘虹2

（1.信阳师范学院计算机与信息技术学院，信阳464000；2.信阳师范学院数学与信息科学学院，信阳464000）

0　引言

最短路径（Shortest Paths，SP）是一种典型的网络优化模型，是解决两结点之间的最小代价问题。许多优化问题，如设备更新、管道铺设、线路安排、厂区布局等，都可转化为网络最短路径问题。算法具体的形式包括：确定起点的最短路径问题、确定终点的最短路径问题、全局最短路径问题等。其次还有一些关于最短路径算法的变形算法相继被提出：多目标最短路径算法［1］、K-最短路径算法［2］、时序最短路径算法［3］等。

用于解决最短路径问题的算法被称做 “最短路径算法”。到目前为止，解决最短路径常用的算法有Dijkstra算法［4］和Floyd算法［5］，以及启发式A*算法［6］等。在这些算法中，Dijkstra算法是典型的单源最短路径算法。

1　Dijkstra算法概述与分析

Dijkstra算法使用了广度优先搜索解决非负权有向图的单源最短路径问题。所谓单源最短路径问题是指：已知图G=（V，E），找出从源结点v1到图中其他各结点的最短路径。Dijkstra算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。对Dijkstra算法的改进是近年来国内外学者研究的热点。例如文献［7］提出了基于改进蚁群算法的最短路径问题；文献 ［8，9］针对多邻接点与多条最短路径提出了改进的Dijkstra算法算法；文献［10］提出了改进的Dijkstra算法在多目标优化中的应用。文献［11］利用分布式稀疏矩阵对Dijkstra算法进行优化。

1.1Dijkstra算法步骤

如果存在一条从源结点v1到vj的最短路径（v1，…，vi，vj），vi是vj前面的一结点，那么（v1，…，vi）也必定是从v1到vi的最短路径。可得从结点v1到达vj的最短距离dist［j］=min｛dist［j］，dist［i］+matrix［i］［j］｝［4］。假设图G= ＜V，E＞，源结点为v1，P=｛v1｝，dist［j］记录v1到vj的最短距离，path［j］记录从v1到vj路径上的vj前面的一个结点。

①从V-P中选择使dist［i］值最小的结点vi，将vi加入到P中；

②更新与vi直接相邻结点vj的dist值。（dist［j］= min｛dist［j］，dist［i］+matrix［i］［j］｝）；

③直到P=V，停止。

1.2Dijkstra算法的不足之处

（1）Dijkstra算法不能解决负权值最短路径问题，如图1所示：

图1　带负权图G1

计算从源结点v1到结点v5的最短路径，用Dijkstra算法得到的结果是v1-v3-v4-v5。主要原因是Dijkstra算法采用的是“标签算法”，而且对于标记过的点不再进行更新。当v3做为距v1距离最短的点加入边集U之后，即使负权值可以使得最短值缩短，程序也不会返回v2重新计算最短路径。

（2）Dijkstra算法需要多次修改结点最短路径的长度。由于算法遍历的结点多，特别是对于稠密图，算法的效率较低。

（3）当从开始点到某个结点之间可能存在多条权重相同的最短路径时，Dijkstra算法没有涉及。Dijkstra算法默认为最短路径上某个结点只有一个前置邻接点，如图2所示，从结点v1到结点v7的最短路径有3条，而用Dijkstra算法只能得到一条最短路径。

图2　带权图G2

为此，本文针对Dijkstra算法的以上几点不足，提出了改进的矩阵迭代标号法，有效地解决Dijkstra算法的以上几点不足之处。

2　矩阵迭代标号法思想步骤

设简单图G=＜V，E＞，V=｛v1，v2，…，vn｝，E=｛e1，e2，…，em｝，由于矩阵在计算机中易于存储和处理，因此可利用矩阵将图表示在计算机中。称n阶方阵A=（aij）n×n为带权图G的距离矩阵。其中：

2.1正图矩阵迭代算法步骤

令dist（l）［j］表示从源结点v1到达结点vj长度≤l的的最短距离。由于最短路径是单向无回路的，所以最短路径最大长度为n-1。为求结点v1到结点vj的最短距离，初始时v1到vj长度为1的最短距离为 a1 j，接着计算v1到vj长度为≤2的最短路径为，以此类推。若n个点分别以1，2，…，n为编号，迭代过程如下：

①取dist（1）［j］为v1到vj长度为1的最短路径，则：

③当dist（l）［j］=dist（l-1）［j］，迭代结束，输出dist（l）［j］=dist ［j］。

定理1：设图G=＜V，E＞，V=｛v1，v2，…，vn｝，E=｛e1，e2，…，em｝且图G为简单带正权图，则迭代序列单调递减收敛于dist［j］，即dist（l）［j］≤dist（l-1）［j］，1≤l≤n-1。

因为单源最短路径是单向无回路的，故当dist（l）［j］= dist（l-1）［j］时，dist（l）［j］=dist［j］。

定理2：对一个具有n个结点m条边的有向图G，若dist（l-1）［j］=dist（l-2）［j］，即第l-1次的迭代结果没有变化（1≤l≤n-1），则迭代过程可提前结束。

当图为正权简单图时，迭代序列（3）可以快捷地找出最短径，但是如果存在从源点可达的负回路，则迭代序列因不能收敛而不能求出最短路径。如图3所示：

图3　带负权图G3

取v1为源结点，利用迭代序列（3）的迭代结果为：

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，…，原因是存在负权值回路造成序列不收敛，不能求出最短路径。

若图中出现权值为负的边，如何避免负权值回路是算法的关键。目前国内外关于这方面的研究结果非常少，美国数学家Richard Bellman和Lester Ford先后提出一种动态规划模式算法Bellman-Ford算法［12］，如果存在dist［u］+w（u，v）＜dist［v］的边，则图中存在负权值回路，程序返回false。Bellman-Ford算法的限制条件是图中不能有负权值的回路，而且公式dist［u］+w（u，v）＜dist［v］是判断回路的必要条件而非充分条件，从而会造成最短路径漏失。

2.2负权图矩阵迭代标号法思想步骤

对一个具有n个结点m条边的简单负权图G，首先对n个点分别编号为1，2，…，n，规定源结点编号为1。构造距离矩阵A=（aij）n×n，令dist（l）［j］表示从源结点1到达结点j的长度≤l的的最短距离。设Aj表示从源结点1到点j的最短路径。U［j］表示从1到j路径上结点的集合。当j=1时，U［1］=｛v1｝；dist（1）［1］=0；当j≠1时，U［j］=｛v1，vj｝，dist（1）［j］=a1j，j=2，3，…，n。utemp［i］表示临时最短路径上节点的集合，utemp［j］的初始值等于U［j］，j=1，2，3，…，n。

①路径长度l=2，并且路径长度l＜=n-1；

②现求从v1到vj路径长度为l的最短路径，对于顶点Vj，有j=2，j＜=n；

③对于任意的aij，如果vj不属于U［i］，b［i］=dist（l-l）［i］+aij，utemp［i］=U［i］∪｛vj｝；否则b［i］=无穷大，utemp［i］=U［i］；

④求b［i］数组的最小值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，转到②；

⑤如果l=n-1，迭代结束，否则l=l+1，转到②。

2.3仿真实验分析

仍以图3中负权图G3为例，v1，v2，v3，v4，v5分别编号为1，2，…，5，用新算法进行迭代，源结点v1到其余结点的最短路径及最短路径权值如表1所示：

表1　新算法的实验结果

dist（3）［j］=dist（2）［j］，迭代提前结束。

2.4算法复杂杂度分析

由于改进算法不存在负权值回路，每次迭代最多需要n-1步，一共最多有n-1次迭代，因此时间复杂度为：

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

算法的最坏时间复杂度为O（n2）。传统的Dijkstra算法每次迭代总共需要不超过2（n-1）2+（n-2）步，一共可能有n-1次迭代，所以：

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

改进算法的时间复杂度低于Dijkstra算法，重要的是当图中存在负权边或负权值回路时，改进算法仍能得到单向无回路的最短路径。

3　应用实例

现信阳市政府需要规划羊山新区的建设工程系统，新区建设主要是由5项子工程构成的：城市交通工程系统、城市供电工程系统、城市绿化工程系统、城市通信工程系统、城市给水工程系统。由于对一项工程的起始条件有着严格的限制，所以每项工程的起始时间并不是很容易确定的。分别用 v1，v2，v3，v4，v5代表以上5项子工程的起始时间（单位：月），工程起始的时间差由8个约束条件组成：v2-v1≥0；v5-v1≥1；v2-v5≤1；v3-v1≤5；v4-v1≤4；v3-v4≥1；v3-v5≥3；v4-v5≥3。

根据本文改进算法知道dist［i］+aij≥dist［j］，可以转化为dist［i］-dist［j］≥-aij，因此可以做以下转化：若vivj≥-k，则建立一条连接xi到xj的边，边权为k；若vsvt≤k，先变形为vt-vs≥-k，再建立一条边权为k的连接vt到vs的边。构建矩阵：

5个点分别编号为1，2，…，5，规定源结点v1=0，迭代结果为：

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

源结点到个结点的最短路径为（0，2，5，4，1），即各项工程开工的最短期限。

4　结语

本文针对Dijkstra算法的缺点和不足，提出了改进的矩阵迭代标号算法。改进算法不仅可以有效求解负权值最短路径问题，而且当从源结点到终点之间可能存在多条权重相同的最短路径时，改进算法可以得到所有的最短路径，此外改进算法采取标号的方法，可以有效解决图中存在负权值回路时的最短路径问题。由于负权值最短路径问题广泛应用于差分约束系统等优化模型中，因此，本文提出的改进算法具有很大的应用价值。另外，在本文的迭代算法中当计算到dist（l）［j］时，dist（l）［1］，dist（l）［2］，…，dist（l）［j-1］都已求得，但却被束之高阁。因新计算出来的分量要比旧分量更优化，如何用新分量代替旧分量dist（l-1）［1］，dist（l-1）［2］，…，dist（l-1）［j-1］，从而提高算法的收敛速度，这将是后续的研究工作。

［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］邓冬梅，王冠楠，朱建等.时序最短路径算法［J］.计算机科学，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］.数学的实践与认识，2013，43（3）：156-164.

［8］王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题［J］.计算机科学，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-），女，硕士，讲师，研究方向为智能计算、信息安全

黄式东（1987-），男，河南信阳人，硕士，助教，研究方向为智能计算

潘虹（1980-），女，山东临沂人，硕士，讲师，研究方向为代数拓扑学

2015-09-01

2015-09-10

最短路径模型是图论研究中的经典问题，针对传统的Dijkstra算法的不足，提出改进的矩阵迭代标号法。改进算法不仅可以有效地求解负权值最短路径问题，而且当两点间存在多条最短路径时，改进算法可以同时得到所有的最短路径。实验结果表明，改进算法的时间复杂度低于传统的Dijkstra算法，且算法简单、易于实现。

Dijkstra算法；最短路径；矩阵算法

国家自然科学基金青年基金（No.11211400）、河南省自然科学基金研究项目（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.