带弧费用约束的最短路径问题

摘要

对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点s,t,找出s和t之间的一条路,使得在满足总费用不超过一个给定正整数的s和t之间所有的路中,该条路的长度最短.通过将背包问题多项式时间变换为该问题的判定问题,证明了该问题是NP-完全的.并给出了求解此问题的一个动态规划算法.最后,我们得到了最优值的一个下界估计.