负权最短路问题的新算法

• 作者: 王铮 韩伟一
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 运筹学 最短路问题 负权 Bellman-Ford算法
• 年，卷（期）: 2007,（1）
• 页码范围: 111-120
• 页数: 10页
• 分类号: O22
• 字数: 7672字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2007.01.013

摘要

Bellman-Ford算法自1958年以来一直是负权最短路问题的公认的最好算法之一.1970年,Yen对其进行了改进,理论上可以节省一半的计算量.本文得到了一种比Bellman-Ford算法更加优越的算法.尽管在理论上新算法无法保证完全超越于Yen的改进算法,但在许多情况下需要更少的计算量.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王铮	中国科学院科技政策与管理科学研究所	202	5346	41.0	66.0
5	韩伟一	中国科学院科技政策与管理科学研究所	3	51	3.0	3.0