求最短路问题的改进算法

《求最短路问题的改进算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第18卷第1期工　科　数　学Vol.18,№.12002年2月JOURNALOFMATHEMATICSFORTECHNOLOGYFeb.2002求最短路问题的改进算法黄祖庆(景德镇陶瓷学院,景德镇333001)[摘　要]本文对图论中含有负权的最短路问题的算法进行了讨论,给出了一个具有“可节省存储空间、提高运算速度、易编程实现”等优点的改进算法(算法三),并通过例题进一步验证了该改进算法的优越性,具有一定的现实意义.[关键词]负权有向图;最短路;Dijkstra算法;改进算法[中图分类号]O15715[文献标识码]A[文章编号]100724120(200

2、2)0120052203　　图论中的最短路问题可描述为:在赋权有向图中,求两个顶点v1到vn之间的一条路,使得在这条路上各个弧的权值之和在从v1到vn的所有路中是最小的.类似的实际问题有许多,如企业的投资决策问题、各种管线的铺设问题、设备更新问题等等,其求解的算法是由Dijkstra在1959年提出的,故称为Dijkstra算法.其基本思路是:假设在得到从v1到vn的最短路之前,已经知道了图中最接近顶点v1的m个顶点,以及从v1到m个顶点的最短路;然后再确定最接近顶点v1的第m+1个顶点vk,以及从点v1到vk的最短路;如此继续延伸,直到vn也被确定,

3、此时问题求解结束.记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)=∞;i

4、i)设顶点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算法标号,称之

5、为第一次标号(此次标号的结果是有可能改变(1)的),记作P.令m=1,转向第二步;(m+1)ii)对图中除v1外的所有点进行第m+1次标号.记P(k)为对顶点vk的第m+1次标号的第二个标号值,其计算公式为:(m+1)(m)(m)P(k)=min{P(k),{P(i)+wikû存在弧(vi,vk)}};[收稿日期]2001202215©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第1期　　　　　　　　　　　黄祖庆:求最短路问题的改进算法53(m+1)(m)iii)若对于每个

6、点,P(k)=P(k)都成立,则找出最短路,算法终止,若对于某些点存在(m+1)(m)P(k)1)个分量P(k)时,已经计算出的最新分(m+1)(m+1)(m+1)量P(2),P(3),⋯,P(k-1)没有被利用.

7、从直观上看,最新计算出来的分量比旧的分量要好些,这就是本文的主体思路,由此得到改进的算法如下(称作算法三):i)先对图中各个顶点按Dijkstra算法标号,称之为第一次标号(此次标号的结果是有可能改变(1)的),记作P.令m=1,转向第二步;(m+1)ii)对图中除v1外的所有点进行第m+1次标号.记P(k)为对顶点vk的第m+1次标号的第二个标号值,其计算公式为:(m+1)(m)(m+1)(m)P(k)=min{P(k),{P(i)+wik,(i≤k);P(i)+wik,(i>k)û存在弧(vi,vk)}};(m+1)(m)iii)若对于每个点,P(

8、k)=P(k)都成立,则找出最短路,算法终止,若对于某些点存在(m+1)(m)P(k)