Premium
An efficient implementation of an algorithm for finding K shortest simple paths
Author(s) -
Hadjiconstantinou E.,
Christofides N.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199909)34:2<88::aid-net2>3.0.co;2-1
Subject(s) - simple (philosophy) , algorithm , computer science , dependency (uml) , quadratic equation , undirected graph , computational complexity theory , time complexity , graph , dependency graph , combinatorics , mathematics , theoretical computer science , philosophy , geometry , software engineering , epistemology
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 [Networks 12 (1982), 411–427], which has the lowest worst‐case complexity of O ( n 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