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

【Abstract】 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.更多还原