摘要
对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点s,t,找出s和t之间的一条路,使得在满足总费用不超过一个给定正整数的s和t之间所有的路中,该条路的长度最短.通过将背包问题多项式时间变换为该问题的判定问题,证明了该问题是NP-完全的.并给出了求解此问题的一个动态规划算法.最后,我们得到了最优值的一个下界估计.
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...
出处
《中国计量学院学报》
2010年第2期167-170,共4页
Journal of China Jiliang University
基金
国家自然科学基金资助项目(No.10601051)
浙江省自然科学基金资助项目(No.Y6090472)
关键词
最短路
判定问题
多项式时间变换
NP-完全
动态规划
shortest path
decision problem
polynomial-time reduction
NP-complete
dynamic programming
