University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Publications

Back to Publications

Author(s) Aljazzar, H., Leue, S.
Title K*: A directed on-the-fly algorithm for finding the k shortest paths
Abstract We present a new algorithm, called K*, for finding the k shortest paths between a designated pair of ver- tices in a given directed weighted graph. Compared to Eppstein’s algorithm, which is the most prominent algorithm for solving this problem, K* has two advan- tages. 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* is a directed al- gorithm which enables the use of heuristic functions to guide the search. This leads to significant improvements in the memory and runtime demands for many practical problem instances. We prove the correctness of K* and show that it maintains a worst-case runtime complexity of O(m+k n log(k n)) and a space complexity of O(k n + m), where n is the number of vertices and m is the number of edges of the graph. We provide experimental results which illustrate the scalability of the algorithm.
Download AlLe08.pdf

Back to Publications