求解单位L∞范数下带值约束的最短路逆问题的算法

An Algorithm for Solving the Shortest Inverse Problem with Value Constraint Under L_∞Norm

研究了单位L_∞范数下带值约束的最短路逆问题,通过将单位L_∞范数下的最短路逆问题转化为求最小平均圈问题,给出了求解单位L_∞范数下带值约束的最短路逆问题的强多项式时间算法,其时间复杂度为O(nm)。利用给出的实例,用二分法的方法验证了论文算法的正确性。

The shortest path inverse problem with value constraint under L_∞norm is studied.By converting the shortest path inverse problem under L_∞norm into the minimum mean cycle problem,a strong polynomial time algorithm for solving the shortest path inverse problem with value constraint under L_∞norm is given,and its time complexity is O(nm).Using the example given,the correctness of the algorithm is verified by dichotomy.