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

摘要

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