"We present a new algorithm, called K*, for ﬁnding the k shortest paths between a designated pair of vertices in a given directed weighted graph. Compared to Eppstein’s algorithm, which is the most prominent algorithm for solving this problem, K* has two advantages. First, K* performs on-the-ﬂy, 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 algorithm which enables the use of heuristic functions

to guide the search. This leads to signiﬁcant 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."

graphs
k-shortest-paths
algorithms
papers
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 algorithm which enables the use of heuristic functions

to guide the search. This leads to signiﬁcant 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."

june 2012 by jm