Publications
Back to Publications
Author(s) 
Aljazzar, H., Leue, S. 
Title 
K*: A directed onthefly 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 onthefly, 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 worstcase 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
