带弧费用约束的最短路径问题

• 作者: 吴龙树
• 来源期刊: 中国计量学院学报
• 学科: 工学
• 关键词: 最短路 判定问题 多项式时间变换 NP-完全 动态规划
• 年，卷（期）: 2010,（2）
• 页码范围: 167-170
• 分类号: TP301.6
• 字数: 3114字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-1540.2010.02.015

摘要

对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点s,t,找出s和t之间的一条路,使得在满足总费用不超过一个给定正整数的s和t之间所有的路中,该条路的长度最短.通过将背包问题多项式时间变换为该问题的判定问题,证明了该问题是NP-完全的.并给出了求解此问题的一个动态规划算法.最后,我们得到了最优值的一个下界估计.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴龙树	中国计量学院理学院	9	17	3.0	3.0