Analysis of LP Relaxations for Multiway and Multicut Problems

In this article, we present an efficient computational implementation of an algorithm for finding the K shortest simple paths connecting a pair of vertices in an undirected graph with n vertices, m arcs, and nonnegative arc lengths. A minimal number of intermediate paths is formed based on the method of Katoh, lbaraki and Mine [Networks 12 (1982), 411-427], which has the lowest worst-case complexity of 0(n to the power of 2) among all other existing algorithms for this problem. A theoretical description of the algorithm is presented with detailed explanations and some examples of the more complicated steps. Efficient data structures for storing and retrieving a large number of paths are given. The results of wide-ranging experimentation with a large number of randomly generated graphs of varying size and density confirm the linear dependency of computing time on K, as proven in Katoh et al., and the quadratic dependency of computing time on graph size as suggested by the worst-case computational complexity. © 1999 John Wiley & Sons, Inc. Networks 34: 88-101, 1999