Premium
Near‐shortest and K‐shortest simple paths
Author(s) -
Matthew Carlyle W.,
Kevin Wood R.
Publication year - 2005
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/net.20077
Subject(s) - shortest path problem , k shortest path routing , combinatorics , subroutine , mathematics , simple (philosophy) , time complexity , floyd–warshall algorithm , algorithm , yen's algorithm , shortest path faster algorithm , discrete mathematics , binary logarithm , path (computing) , computer science , graph , dijkstra's algorithm , philosophy , epistemology , operating system , programming language
We present a new algorithm for enumerating all near‐shortest simple (loopless) s ‐ t paths in a graph G = ( V , E ) with nonnegative edge lengths. Letting n = | V | and m = | E |, the time per path enumerated is O ( n S ( n , m )) given a user‐selected shortest‐path subroutine with complexity O ( S ( n , m )). When coupled with binary search, this algorithm solves the corresponding K ‐shortest paths problem (KSPR) in O ( K n S ( n , m )(log n + log c max )) time, where c max is the largest edge length. This time complexity is inferior to some other algorithms, but the space complexity is the best available at O ( m ). Both algorithms are easy to describe, to implement and to extend to more general classes of graphs. In computational tests on grid and road networks, our best polynomial‐time algorithm for KSPR appears to be at least an order of magnitude faster than the best algorithm from the literature. However, we devise a simpler algorithm, with exponential worst‐case complexity, that is several orders of magnitude faster yet on those test problems. A minor variant on this algorithm also solves “KSPU,” which is analogous to KSPR but with loops allowed. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 98–109 2005