The shortest and the K-shortest routes as assignment problems

✍ Scribed by A. Weintraub

• Publisher: John Wiley and Sons
• Year: 1973
• Tongue: English
• Weight: 552 KB
• Volume: 3
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230030105

✦ Synopsis

Abstract

The 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(m^3^). 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(m^2.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(m^2^) 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(Km^3^) in both cases.