第18卷第1期工 科 数 学Vol.18,№.1
2002年2月JOURNALOFMATHEMATICSFORTECHNOLOGYFeb.2002
求最短路问题的改进算法
黄祖庆
(景德镇陶瓷学院,景德镇333001)
[摘 要]本文对图论中含有负权的最短路问题的算法进行了讨论,给出了一个具有“可节省存储空间、提高运算速度、易编程实现”等优点的改进算法(算法三),并通过例题进一步验证了该改进算法的优越性,具有一定的现实意义.[关键词]负权有向图;最短路;Dijkstra算法;改进算法[中图分类号]O157.5 [文献标识码]A [文章编号]1007-4120(2002)01-0052-03
图论中的最短路问题可描述为:在赋权有向图中,求两个顶点v1到vn之间的一条路,使得在
这条路上各个弧的权值之和在从v1到vn的所有路中是最小的.
类似的实际问题有许多,如企业的投资决策问题、各种管线的铺设问题、设备更新问题等等,其求解
的算法是由Dijkstra在1959年提出的,故称为Dijkstra算法.其基本思路是:假设在得到从v1到vn的
最短路之前,已经知道了图中最接近顶点v1的m个顶点,以及从v1到m个顶点的最短路;然后再确定
最接近顶点v1的第m+1个顶点vk,以及从点v1到vk的最短路;如此继续延伸,直到vn也被确定,此时
问题求解结束.
记P,T分别为永久标号集和临时标号集.顶点vi的临时标号记成T(i),它表示从v1到vi的最短
距离的上界;顶点vi的永久标号记成P(i),它表示从v1到vi的实际最短距离.已得到P类标号的顶点
不再改变其标号,而没有标上P类标号的顶点必须标上T类标号.算法的每一步要把某一顶点的T类
标号改为P类标号.当vn获得P类标号时,就求得了从v1到vn的最短路线.wij为弧(vi,vj)的权值.则
Dijkstra算法具体步骤为(称作算法一):
i)给顶点v1标上永久标号P(1)=0,这表示从v1到v1最短距离为零.其余顶点标上临时标号T(j)=∞;
ii)设顶点i是刚得到P类标号的顶点,把与顶点i有弧直接相连而又属于T类标号的各顶点j的
标号改为下列T类标号:
T(j)=min{T(j),P(i)+wij};
iii)在T类标号中选标号最小的顶点j0,并把它的临时标号T(j0)改为永久标号P(j0).若终点获
得P类标号,则算法终止,最短路已经找到;否则转向ii).
Dijkstra的思路、算法简单,但是仅适用权值wij≥0的情形.当权值wij有负值时,此时须对Dijkstra
算法作些改动、补充,则仍可以求出含有负权值图的最短路,算法步骤如下(称作算法二):
i)先对图中各个顶点按Dijkstra算法标号,称之为第一次标号(此次标号的结果是有可能改变
的),记作P(1).令m=1,转向第二步;
ii)对图中除v1外的所有点进行第m+1次标号.记P(m+1)(k)为对顶点vk的第m+1次标号的第二个标号值,其计算公式为:
P(m+1)(k)=min{P(m)(k),{P(m)(i)+wik|存在弧(vi,vk)}};
[收稿日期]2001-02-15iii)若对于每个点,P(m+1)(k)=P(m)(k)都成立,则找出最短路,算法终止,若对于某些点存在
P(m+1)(k) 从上述算法中不难发现,若图中有负权,则求最短路的算法实际上是一个迭代算法,在迭代的每一 步计算过程中是用P(m)={P(m)(2),P(m)(3),…,P(m)(n)}的全部分量来计算P(m+1)={P(m+1)(2), P(m+1)(3),…,P(m+1)(n)}的全部分量,显然在计算第k(k>1)个分量P(m+1)(k)时,已经计算出的最新分 量P(m+1)(2),P(m+1)(3),…,P(m+1)(k-1)没有被利用.从直观上看,最新计算出来的分量比旧的分量要好些,这就是本文的主体思路,由此得到改进的算法如下(称作算法三): i)先对图中各个顶点按Dijkstra算法标号,称之为第一次标号(此次标号的结果是有可能改变 的),记作P(1).令m=1,转向第二步; ii)对图中除v1外的所有点进行第m+1次标号.记P(m+1)(k)为对顶点vk的第m+1次标号的第二个标号值,其计算公式为: P(m+1)(k)=min{P(m)(k),{P(m+1)(i)+wik,(i≤k);P(m)(i)+wik,(i>k)|存在弧(vi,vk)}}; iii)若对于每个点,P(m+1)(k)=P(m)(k)都成立,则找出最短路,算法终止,若对于某些点存在 P(m+1)(k) 其算法框图为: 从本算法及算法框图知其最大的一个优点是,在计算机编程实现时,只需一组存储单元,比前一算 法节省了近一半存储单元,且可节省计算时间.下面通过例子加以说明. 例 在下图中,求从v1到v4的最短路. 解 第一次标号的结果为(即利用算法一): P(1)={P(1)(1),P(1)(2),P(1)(3),P(1)(4)}={0,2,3,1} (由于有负权,故需要进一步修正). (一)利用算法二:i)对v2,v3,v4进行第二次标号,计算如下:P(2)(2)=min{P(1)(2),P(1)(3)+w32}=min{2,3-2}=53第1期 黄祖庆:求最短路问题的改进算法1,P(2)(3)=min{P(1)(3)}=3,P(2)(4)=min{P(1)(4),P(1)(2)+w24,P(1)(3)+ w34}=min{1,2-1,3+5}=1,所以第二次标号结果为P(2)={P(1)(1),P(2) (2),P(2)(3),P(2)(4)}={0,1,3,1}; ii)第三次标号的结果为P(3)={P(1)(1),P(3)(2),P(3)(3),P(3)(4)}={0, 1,3,0}; iii)第四次标号的结果为P(3)={P(1)(1),P(3)(2),P(3)(3),P(3)(4)}={0, 1,3,0},与第三次标号的结果完全相同,故此时算法终止,经逆向追踪得到所要求的最短路为P={v1, v3,v2,v4},其最短路长为零. (二)利用算法三 i)次开发对v2,v3,v4进行第二次标号,计算如下:P(2)(2)=min{P(1)(2),P(1)(3)+w32}=min{2,3 -2}=1,p(2)(3)=min{P(1)(3)}=3,P(2)(4)=min{P(1)(4),P(2)(2)+w24,P(2)(3)+w34}=min{1,1- 1,3+5}=0,所以第二次标号结果为P(2)={P(1)(1),P(2)(2),P(2)(3),P(2)(4)}={0,1,3,0}, ii)第三次标号的结果为P(3)={P(1)(1),P(3)(2),P(3)(3),P(3)(4)}={0,1,3,0},与第二次标号的 结果完全相同,故此时算法终止,经逆向追踪得到所要求的最短路为P={v1,v3,v2,v4},其最短路长为零. [参 考 文 献] [1] 沈荣芳.运筹学[M].北京:机械工业出版社,1997.[2] 钱颂迪.运筹学[M].北京:清华大学出版社,1999.[3] 李庆扬、王能超、易大义.数值分析[M].武汉:华中理工大学出版社,1986.54工 科 数 学 第18卷