一类变形的反最短路问题  

A Variation of the Inverse Shortest Paths Problem

作　　者：杨超[1] 孙静娟[1] 

机构地区：[1]华中科技大学

出　　处：《武汉工业大学学报》2001年第3期87-89,共3页

基　　金：国家自然科学基金资助项目 (70 0 710 11)

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

关 键 词：最短线路 多项式算法 变形 反量短线路 

分 类 号：O221[理学—运筹学与控制论]