中文摘要：

对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点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...