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

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 slain 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 + n log n + 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. (C) 2011 Elsevier B.V. All rights reserved.