AE 2010: 5. Vorlesung (18. Mai)
Kürzeste Wege Suche in Straßennetzwerken
Dijkstra's
Originalpaper von 1959
zu seinem SSSP-Algorithmus
Der bidirektionale Dijkstra wurde im Buch
Linear Programming and Extensions
von Dantzig vorgestellt.
Straßennetzwerke
, die im Rahmen der
9. DIMACS Implementation Challenge
zur Verfügung gestellt wurden (u.a. Europe von der PTV AG).
A*-Suche
im Umfeld von KI:
Doran & Michie (1966)
Originalartikel:
Hart, Nilsson & Raphael (1968)
Überblick zu Speedup-Techniken
Übersichtsartikel von
Delling, Sanders, Schultes & Wagner (2009)
auch interessant:
Folien
von Goldberg zu klassischen und aktuellen Techniken
Multilevel-Methoden:
Schulz, Wagner & Weihe (1999)
Reach-basiertes Routing:
Gutman (2004)
Highway-Hierarchies:
Sanders & Schultes (2005)
fortgeschrittenes Reach-basiertes Routing:
Goldberg, Kaplan & Werneck (2006)
Highway-Node-Routing:
Schultes & Sanders (2007)
Contraction-Hierarchies:
Geisberger et al. (2008)
Entfernungstabellen:
Sanders & Schules (2006)
Transit-Knoten Routing:
Delling et al. (2008)
,
Bast et al. (2007)
,
Sanders & Schultes (2008)
Kanten-Label:
Schulz, Wagner & Weihe (1999)
SHARC:
Bauer & Delling (2008)
Landmark A*:
Goldberg & Harrelson (2005)
,
Technical Report