| 带弧费用约束的最短路径问题 |
| |
| 引用本文： | 吴龙树.带弧费用约束的最短路径问题[J].中国计量学院学报,2010,21(2). |
| |
| 作者姓名： | 吴龙树 |
| |
| 作者单位： | 中国计量学院,理学院,浙江,杭州,310018 |
| |
| 基金项目： | 国家自然科学基金资助项目，浙江省自然科学基金资助项目 |
| |
| 摘 要： | 对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点s,t,找出s和t之间的一条路,使得在满足总费用不超过一个给定正整数的s和t之间所有的路中,该条路的长度最短.通过将背包问题多项式时间变换为该问题的判定问题,证明了该问题是NP-完全的.并给出了求解此问题的一个动态规划算法.最后,我们得到了最优值的一个下界估计.
|
| 关 键 词： | 最短路 判定问题 多项式时间变换 NP-完全 动态规划 |
The shortest path problem with cost restriction on edges |
| |
| WU Long-shu.The shortest path problem with cost restriction on edges[J].Journal of China Jiliang University,2010,21(2). |
| |
| Authors: | WU Long-shu |
| |
| Affiliation: | WU Long-shu(College of Sciences; China Jiliang University; Hangzhou 310018; China); |
| |
| Abstract: | A kind of the shortest path problem with cost restriction on edges was studied to find a path between two given vertices s and t in a network,such that the length of this path was the shortest among all the paths between s and t with total cost not exceeding a given positive integer.It was shown that this problem was NP-complete by a polynomial-time reduction from the knapsack problem.A dynamic programming method was presented to solve this problem.And finally an estimation of the lower bound for the optima... |
| |
| Keywords: | shortest path decision problem polynomial-time reduction NP-complete dynamic programming |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
