带弧费用约束的最短路径问题 (2010年)

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