K^⁎ : A heuristic search algorithm for finding the k shortest paths

Abstract

We present a directed search algorithm, called K⁎, for finding the k shortest paths between a designated pair of vertices in a given directed weighted graph. K⁎ has two advantages compared to current k-shortest-paths algorithms. First, K⁎ operates on-the-fly, which means that it does not require the graph to be explicitly available and stored in main memory. Portions of the graph will be generated as needed. Second, K⁎ can be guided using heuristic functions. We prove the correctness of K⁎ and determine its asymptotic worst-case complexity when using a consistent heuristic to be the same as the state of the art, O(m+nlogn+k), with respect to both runtime and space, where n is the number of vertices and m is the number of edges of the graph. We present an experimental evaluation of K⁎ by applying it to route planning problems as well as counterexample generation for stochastic model checking. The experimental results illustrate that due to the use of heuristic, on-the-fly search K⁎ can use less time and memory compared to the most efficient k-shortest-paths algorithms known so far.