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

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

0.00 Avg rating0 Votes
Article ID: iaor20022495
Country: United States
Volume: 34
Issue: 2
Start Page Number: 88
End Page Number: 101
Publication Date: Sep 1999
Journal: Networks
Authors: ,
Abstract:

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, Ibaraki and Mine, which has the lowest worst-case complexity of O(n2) 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.

Reviews

Required fields are marked *. Your email address will not be published.