求最短路问题的改进算法.pdfVIP

第 18 卷第 1 期 工　科　数　学 . 18, №. 1 V o l 2002 年 2 月 JOU RNAL O F M A TH EM A T ICS FOR T ECHNOLO GY Feb. 2002 求最短路问题的改进算法 黄祖庆 (景德镇陶瓷学院, 景德镇 333001) 　　[摘　要] 本文对图论中含有负权的最短路问题的算法进行了讨论, 给出了一个具有“可节省存储空间、提高运算速 ( ) 度、易编程实现”等优点的改进算法 算法三 , 并通过例题进一步验证了该改进算法的优越性, 具有一定的现实意义. [ 关键词] 负权有向图; 最短路; D ijk stra 算法; 改进算法 [ 中图分类号] O 1575　　[ 文献标识码] A 　　[ 文章编号] (2002) 　　图论中的最短路问题可描述为: 在赋权有向图中, 求两个顶点 v 1 到 v n 之间的一条路, 使得在 这条路上各个弧的权值之和在从 v 1 到 v n 的所有路中是最小的. 类似的实际问题有许多, 如企业的投资决策问题、各种管线的铺设问题、设备更新问题等等, 其求解 的算法是由D ijk stra 在 1959 年提出的, 故称为D ijk stra 算法. 其基本思路是: 假设在得到从 v 1 到 v n 的 最短路之前, 已经知道了图中最接近顶点v 1 的m 个顶点, 以及从v 1 到m 个顶点的最短路; 然后再确定 最接近顶点 1 的第 + 1 个顶点 k , 以及从点 1 到 k 的最短路; 如此继续延伸, 直到 n 也被确定, 此时 v m v v v v 问题求解结束. 记 , 分别为永久标号集和临时标号集. 顶点 的临时标号记成 ( ) , 它表示从 到 的最短 P T v i T i v 1 v i 距离的上界; 顶点 的永久标号记成 ( ) , 它表示从 到 的实际最短距离. 已得到 类标号的顶点 v i P i v 1 v i P 不再改变其标号, 而没有标上 P 类标号的顶点必须标上 T 类标号. 算法的每一步要把某一顶点的 T 类 标号改为 P 类标号. 当v n 获得P 类标号时, 就求得了从 v 1 到 v n 的最短路线. w ij 为弧(v i , vj ) 的权值. 则 ( ) D ijk stra 算法