An efficient implementation of an algorithm for finding K shortest simple paths

In this article, we present an efficient computational implementation of an algorithm for finding the K shortest simple paths connecting a pair of ver tices in an undirected graph with n vertices, m arcs, and nonnegative are l engths. A minimal number of intermediate paths is formed based on the metho d of Katoh, Ibaraki and Mine [Networks 12 (1982), 411-427], which has the l owest worst-case complexity of O(n(2)) among all other existing algorithms for this problem. A theoretical description of the algorithm is presented w ith detailed explanations and some examples of the more complicated steps. Efficient data structures for storing and retrieving a large number of path s are given. The results of wide-ranging experimentation with a large numbe r of randomly generated graphs of varying size and density confirm the line ar dependency of computing time on K, as proven in Katoh et al., and the qu adratic dependency of computing time on graph size as Suggested by the wors t-case computational complexity. (C) 1999 John Wiley & Sons, Inc.