于成成 周泽聿 张斌武

（1.河海大学企业管理学院 常州 213022）（2.河海大学常州校区数理教学部 常州 213022）

1 引言

最短路问题是一类很重要的问题，其逆问题也具有很大的研究价值，它们在交通网络、通信网络等实际问题中有着广泛的应用。同时很多网络问题的逆问题也可能转化成最短路逆问题，最短路逆问题的解决有助于许多其他网络问题的解决。

近年来，最短路逆问题受到众多学者的关注，相关学者在最短路逆问题上也取得了一些进展。D.Burton 和Ph.LTiont［1］首先提出最短路逆问题，并使用二次规划的算法来求解L2范数下的最短路逆问题。Zhang Jianzhong等［2］引入列生成算法来求解单位L1范数下的最短路逆问题。Ahuja等［3］将单位L1范数下的最短路逆问题转化为最短路问题，从而得到了一个强多项式时间算法；将单位L∞范数下的最短路逆问题转化为最小平均圈问题；将非单位L∞范数下的最短路逆问题转化为最小费用和时间比例图问题。Xu Shaoji 等［4］将非单位权重下的最短路逆问题转化为最小费用流问题。在有值约束的条件下，Burton等［5］证明了非单位L2范数下带值约束的最短路逆问题是NP完全问题。张斌武等［6～11］研究Hamming 距离下各种网络的最短路逆问题及改进问题，对一些特殊网络给出了强多项式时间算法及近似算法，并证明了Hamming距离下一般网络的最短路逆问题是NP 困难的。除此之外，还有学者［12～14］研究了其他约束条件下的最短路逆问题，取得了一些进展。

本文研究单位L∞范数下带值约束的最短路逆问题，要求调整边长度向量，使得给定路径P0为新长度向量下图G的最短路径，且在新长度向量下P0的长度不超过给定的上界，并使得边长度的最大改变量最小。……