一类双约束最短路问题的近似算法

Approximation Scheme for a Kind of Shortest Path Problem with Two Additional Constraints

带时间和边数约束的双约束最短路问题是NP 完备的 .它的一种拟多项式精确算法可以利用动态规划方法给出 ,在此基础上采用rounding和scaling的处理技术得到了一种全多项式时间近似方案 (FPAS) .

The shortest path problem with two additional constraints in transition time and number of edges is NP Complete.A pseudo-polynomial exact algorithm for it is presented by using dynamic programming method.On the basis of this,a fully polynomial approximation scheme(EPAS)is provided through the techniques of rounding and scaling.