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

Aljazzar, Husain; Leue, Stefan

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

Dateien

K_A_Directed_On_The_Fly_Algorithm_for_Finding_the_k_Shortest_Paths.pdfGröße: 253.34 KBDownloads: 221

Datum

2008

Autor:innen

Aljazzar, Husain

Leue, Stefan

Schriftenreihe

Technical Report, Chair for Software Engineering, University of Konstanz

URI (zitierfähiger Link)

http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-57829

Link zur Lizenz

Urheberrechtlich geschützt

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Working Paper/Technical Report

Publikationsstatus

Published

Zusammenfassung

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
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.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

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

BibTex

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

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/5575">
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:creator>Aljazzar, Husain</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Aljazzar, Husain</dc:contributor>
    <dc:format>application/pdf</dc:format>
    <dc:language>eng</dc:language>
    <dc:rights>terms-of-use</dc:rights>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5575/1/K_A_Directed_On_The_Fly_Algorithm_for_Finding_the_k_Shortest_Paths.pdf"/>
    <dc:creator>Leue, Stefan</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:56:32Z</dcterms:available>
    <dcterms:issued>2008</dcterms:issued>
    <dcterms:abstract xml:lang="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&lt;br /&gt;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.</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5575/1/K_A_Directed_On_The_Fly_Algorithm_for_Finding_the_k_Shortest_Paths.pdf"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Leue, Stefan</dc:contributor>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5575"/>
    <dcterms:title>K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths</dcterms:title>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:56:32Z</dc:date>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja