点带约束成本的最短路问题

• 作者: 何勇 姚恩瑜 李帮义
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 最短路问题 计算复杂性 算法
• 年，卷（期）: 2000,（1）
• 页码范围: 93-96
• 页数: 4页
• 分类号: O224
• 字数: 2594字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2000.01.015

摘要

本文提出了点带约束成本的最短路问题.证明了该问题是NP-完全的,并利用动态规划给出了一个伪多项式算法.对所有顶点约束成本相同的情况,给出了一个时间复杂性为O(mn2)的算法.对最小点成本最短路问题,给出了一个时间复杂性为O(n2)的算法.

作者信息

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