Finding the k Shortest Simple Paths: A New Algorithm and its Implementation

摘要

We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed recently by Hershberger and Suri, and can yield a factor Θ(n) improvement for this problem. But there is a caveat: the fast replacement paths subroutine is known to fail for some directed graphs. However, the failure is easily detected, and so our k shortest paths algorithm optimistically uses the fast subroutine, then switches to a slower but correct algorithm if a failure is detected. Thus the algorithm achieves its Θ(n) speed advantage only when the optimism is justified. Our empirical results show that the replacement paths failure is a rare phenomenon, and the new algorithm outperforms the current best algorithms; the improvement can be substantial in large graphs. For instance, on GIS map data with about 5000 nodes and 12000 edges, our algorithm is 4-8 times faster. In synthetic graphs modeling wireless ad hoc networks, our algorithm is about 20 times faster.