带多重选择的最短路问题:复杂性和算法

• 作者: 姚恩瑜 李帮义
• 来源期刊: 数学杂志
• 学科: 数学
• 关键词: 多重选择 最短路 算法 NP-C
• 年，卷（期）: 2000,（3）
• 页码范围: 300-304
• 页数: 5页
• 分类号: O124
• 字数: 3380字
• 语种: 中文
• DOI: 10.3969/j.issn.0255-7797.2000.03.012

摘要

本文提出了带多重选择的最短路问题,建立了该问题的数学模型.利用背包问题的一个变形问题--带限制选择的背包问题,证明了该问题是NP-C的.最后利用动态规划给出了一个伪多项式算法,其时间复杂性O(Chmn),其中h是最大的选择重数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姚恩瑜	浙江大学应用数学系	17	117	5.0	10.0
2	李帮义	浙江大学应用数学系	5	48	3.0	5.0