K* : heuristics-guided, on-the-fly k shortest paths search

Abstract

We present a search algorithm, called K*, for finding the k shortest paths (KSP) between a designated pair of vertices in a given directed weighted graph. As a directed algorithm, K* has two advantages compared to current KSP algorithms. First, K* performs 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 discuss the properties of K*, including its correctness, and its asymptotic worst-case complexity, which has been shown to be of 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 report on experimental results which illustrate the favorable performance of K* compared to the most efficient k-shortest-paths algorithms known so far. In other work it has been shown that K* can be used to efficiently compute counterexamples for stochastic model checking.