K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:adab7e6c9ac00341f1e25aadd08c3391

ALJAZZAR, Husain, Stefan LEUE, 2008. K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths

@techreport{Aljazzar2008Direc-5575, series={Technical Report, Chair for Software Engineering, University of Konstanz}, title={K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths}, year={2008}, number={soft-08-03}, author={Aljazzar, Husain and Leue, Stefan} }

deposit-license 2008 eng We present a new algorithm, called K*, for finding 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-fly, which means that<br />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 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. Leue, Stefan Aljazzar, Husain application/pdf Aljazzar, Husain Leue, Stefan K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths 2011-03-24T15:56:32Z 2011-03-24T15:56:32Z

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

K_A_Directed_On_The_Fly_Algorithm_for_Finding_the_k_Shortest_Paths.pdf 115

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto