| Dijkstra's Algorithm | |
| [Dij59] |
Edsger W. Dijkstra.
A note on two problems in connexion with graphs.
Numerische Mathematik, 1:269-271, 1959. [ bib ] |
| [Dij] |
Edsger W. Dijkstra.
Reflections on ``a note on two problems in connexion with graphs''.
Source: http://www.cs.utexas.edu/ EWD/. [ bib | Pdf ] |
| [Dan60] |
George B. Dantzig.
On the shortest route through a network.
Management Science, 6:187-190, 1960. [ bib ] |
| Moore-Bellmann-Ford Algorithm | |
| [For56] |
Lester R. Ford.
Network flow theory.
Technical Report Paper P-923, The Rand Corporation, Santa Monica,
1956. [ bib ] |
| [Bel58] |
Richard Bellmann.
Quarterly of Applied Mathematics, 16:87-90, 1958. [ bib ] |
| [Moo59] |
Edward F. Moore.
The shortest path through a maze.
In Proceedings of the International Symposium on the Theory of
Switching, pages 285-292. Harvard University Press, 1959. [ bib ] |
| Highway Hierarchies | |
| [SS05] |
Peter Sanders and Dominik Schultes.
Highway hierarchies hasten exact shortest path queries.
In Proceedings 17th European Symposium on Algorithms (ESA),
volume 3669 of Springer LNCS, pages 568-579. Springer, 2005. [ bib | Pdf ] |
| Goal-directed search and preprocessing variants | |
| [HNR68] |
P. E. Hart, N. J. Nilsson, and B. Raphael.
A formal basis for the heuristic determination of minimum cost paths
in graphs.
IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107,
1968. [ bib ] |
| [GH05] |
Andrew Goldberg and Chris Harrelson.
Computing the shortest path: A* search meets graph theory.
In Proceedings of the 16th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 2005). SIAM, 2005. [ bib | Pdf ] |
| [GW05] |
Andrew Goldberg and R. Werneck.
Computing point-to-point shortest paths from external memory.
In Proceedings Workshop on Algorithm Engineering and Experiments
(ALENEX 2005). SIAM, 2005. [ bib | Pdf ] |
| Geometric Containers | |
| [WW03] |
Dorothea Wagner and Thomas Willhalm.
Geometric speed-up techniques for finding shortest paths in large
sparse graphs.
In Proc. 11th European Symposium on Algorithms (ESA), volume
2832 of LNCS, pages 776-787. Springer, 2003. [ bib | Pdf ] |
| [KMS04] |
Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling.
Acceleration of shortest path computation.
Article 42, Technische Universität Berlin, Fakultät II
Mathematik und Naturwissenschaften, 2004. [ bib | Url ] |
| [Lau04] |
U. Lauther.
An extremely fast, exact algorithm for finding shortest paths in
static networks with geographical background.
In Geoinformation und Mobilität - von der Forschung zur
praktischen Anwendung, volume 22, pages 219-230. IfGI prints, Institut
für Geoinformatik, Münster, 2004. [ bib | Url | Pdf ] |
| [MSS+05] |
Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and
Thomas Willhalm.
Partitioning graphs to speed up Dijkstra's algorithm.
In WEA, pages 189-202, 2005. [ bib | Url | Pdf ] |
| Partition-based hierarchical techniques | |
| [JHR98] |
Ning Jing, Yun-Wu Huang, and Elke A. Rundensteiner.
Hierarchical encoded path views for path query processing: An optimal
model and its performance evaluation.
IEEE Trans. Knowledge and Data Engineering, 10(3), 1998. [ bib | Url ] |
| [JP02] |
Sungwon Jung and Sakti Pramanik.
An efficient path computation model for hierarchically structured
topographical road maps.
IEEE Trans. Knowledge and Data Engineering, 14(5), 2002. [ bib ] |
| [HSW06] |
Martin Holzer, Frank Schulz, and Dorothea Wagner.
Engineering multi-level overlay graphs for shortest-path queries.
In Proceedings of the Eighth Workshop on Algorithm Engineering
and Experiments (ALENEX). SIAM, 2006.
To appear. [ bib | Pdf ] |
| Reach-based routing | |
| [Gut04] |
R. Gutman.
Reach-based routing: A new approach to shortest path algorithms
optimized for road networks.
In Proceedings 6th Workshop on Algorithm Engineering and
Experiments (ALENEX), pages 100-111. SIAM, 2004. [ bib | Pdf ] |
| Applications in Timetable Information | |
| [SWW00] |
Frank Schulz, Dorothea Wagner, and Karsten Weihe.
Dijkstra's algorithm on-line: An empirical case study from public
railroad transport.
J. Experimental Algorithmics, 5(12), 2000. [ bib | Pdf ] |
| [SWZ02] |
Frank Schulz, Dorothea Wagner, and Christos Zaroliagis.
Using multi-level graphs for timetable information in railway
systems.
In Proceedings 4th Workshop on Algorithm Engineering and
Experiments (ALENEX), volume 2409 of LNCS, pages 43-59. Springer,
2002. [ bib | Pdf ] |
| Surveys and combinations | |
| [HSW04] |
Martin Holzer, Frank Schulz, and Thomas Willhalm.
Combining speed-up techniques for shortest-path computations.
In Proceedings Third International Workshop on Experimental and
Efficient Algorithms (WEA), volume 3059 of LNCS, pages 269-284.
Springer, 2004. [ bib | Pdf ] |
| [GKW06] |
Andrew Goldberg, Haim Kaplan, and Renato Werneck.
Reach for A*: Efficient point-to-point shortest path algorithms.
In Proceedings of the Eighth Workshop on Algorithm Engineering
and Experiments (ALENEX06). SIAM, 2006.
To appear. [ bib | Pdf ] |
| [WW06] |
Thomas Willhalm and Dorothea Wagner.
Shortest path speedup techniques.
In Algorithmic Methods for Railway Optimization, LNCS.
Springer, 2006.
To appear. [ bib ] |
| Theses | |
| [Buc00] |
Friedhelm Buchholz.
Hierarchische Graphen zur Wegesuche.
PhD thesis, Fakultät für Informatik der Universität Stuttgart,
2000. [ bib ] |
| [Hol03] |
Martin Holzer.
Hierarchical speed-up techniques for shortest-path algorithms.
Master's thesis, Universität Konstanz, Fachbereich Informatik und
Informationswissenschaft, 2003. [ bib | Url ] |
| [Fli04] |
Ingrid C.M. Flinsenberg.
Route Planning Algorithms for Car Navigation.
PhD thesis, Technische Universiteit Eindhoven, 2004. [ bib ] |
| [Sch05b] |
Frank Schulz.
Timetable Information and Shortest Paths.
PhD thesis, Universität Karlsruhe (TH), Fakultät Informatik,
2005. [ bib | Url | Ps | Pdf ] |
| [Wil05] |
Thomas Willhalm.
Engineering Shortest Paths and Layout Algorithms for Large
Graphs.
PhD thesis, Universität Karlsruhe (TH), Fakultät Informatik,
2005. [ bib | Url | Pdf ] |
| [Sch05a] |
Dominik Schultes.
Highway hierarchies hasten exact shortest path queries.
Master's thesis, Universität Karlsruhe (TH), Fakultät Informatik,
2005. [ bib | Url ] |
| [OR90] |
A. Orda and R. Rom.
Shortest-path and minimum-delay algorithms in networks with
time-dependent edge-length.
Journal of the ACM, 37(3):607-625, 1990. [ bib | Url ] |
| [OR91] |
A. Orda and R. Rom.
Minimum weight paths in time-dependent networks.
Networks, 21:295-319, 1991. [ bib | Url ] |
| [Nac95] |
Karl Nachtigal.
Time depending shortest-path problems with applications to railway
networks.
European Journal of Operations Research, 83:154-166, 1995. [ bib | Url ] |