The shortest and the K‐shortest routes as assignment problems
作者:
A. Weintraub,
期刊:
Networks
(WILEY Available online 1973)
卷期:
Volume 3,
issue 1
页码: 61-73
ISSN:0028-3045
年代: 1973
DOI:10.1002/net.3230030105
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThe problem of finding a shortest route in a network with unrestricted costs is approached through solving an assignment problem associated to the network.The upper bound on the number of elementary calculations required for the solution is 0(m3). However, in most cases, the actual number of computations is considerably less and depends on different network characteristics than Dynamic Programming algorithms do. In examples of networks generated stochastically, this number was below 0(m2.5).A parametric analysis is presented. It is shown that if after a shortest route is determined, the costs on all arcs incident into or out of a node are modified in any form, at most 0(m2) elementary calculations will determine a new optimal solution. This feature, shared by Dynamic Programming algorithms only for cases where all cost decrease, can be applied to problems such as the determination of the K‐shortest routes and the K‐smallest assignments, leading to upper bounds of 0(Km3) in both ca
点击下载:
PDF
(551KB)
返 回