带负权最短路问题前趋法的改进

• 作者: 孙小军 王志强
• 来源期刊: 安徽大学学报(自然科学版)
• 学科: 工学
• 关键词: 有向网络 负权 最短路 前趋法 动态规划
• 年，卷（期）: 2009,（2）
• 页码范围: 27-30
• 页数: 4页
• 分类号: TP301.6
• 字数: 2916字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-2162.2009.02.008

摘要

针对在带负权的有向网络中求最短路的前趋法的不足,结合动态规划思想从提高算法效率方面对其进行了改进,并提出了一种新算法.新算法通过引入变量记录当前节点到宿节点的最短路权,避免了前趋法中比较多条前趋路时反复计算最短路的冗余运算,同时弥补了动态规划不能直接求解带回路的有向网络最短路的缺陷,是一种计算带负权最短路问题的简便方法.该算法对非负权网络中的最短路问题同样有效.最后仿真结果和算例表明了新算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙小军	宝鸡文理学院数学系	57	242	9.0	11.0
2	王志强	国防科技大学信息系统与管理学院	3	7	1.0	2.0