一类变形的反最短路问题

A Variation of the Inverse Shortest Paths Problem

考虑了一类变形的反最短路问题 ,即在一种点调整约束的条件下 ,如何对网络的权向量进行尽可能少的调整 ,使得给定的路变为最短线路。对这类问题提出一种强多项式算法。

In this paper we consider a kind of the inverse shortest paths problem in which we want to adjust the given weights of arcs as less as possible so that a set of given paths become shortest ones from their sources to sinks, under an additional requirement that the weights of all arcs initiated from the same node must be adjusted by the same amount. We first formulate this problem into an LP model, them prove it can be solved in strongly polynomial time.