Ultrafast shortest-path queries via transit nodes
Holger Bast, Stefan Funke, Domagoj Matijević · DIMACS series in discrete mathematics and theoretical computer science · 2009
Die klassische Losung zur Berechnung kurzester Wege ist die Anwendung des Dijkstra Algorithmus, der in O(m + n log m) Zeit selbigen findet, wobei m die Anzahl Kanten ist und n die Anzahl der Knoten. Fur die Berechnung zwischen zwei beliebigen Knoten im US-Strasennetzwerk, bestehend aus ca. 24 Mio. Knoten und ca. 58 Mio. Kanten, dauert dies auf heutigen Rechnern mehr als eine Sekunde. Fur viele Anwendungen ist dies zu langsam. Obwohl es noch eine offene Frage ist, ob Dijkstra [1] fur solche Anfragen optimal ist, gibt es eine offensichtliche untere Schranke von Ω(m + n). Um schnellere, sublineare, Anfragezeiten zu erreichen, mus eine Vorverarbeitung stattfinden. Holger Bast et al. [2] stellten das Transitknoten-Konzept – ein allgemeines Konzept zur Auswahl einer Menge an Strasenknoten fur eine Vorberechnung – vor, auf welches im Folgenden naher eingegangen wird.