 | The ACM Journal of Experimental Algorithmics |
Volume 5, Article 12, 2000
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport
by
and
and
http://www.jea.acm.org/2000/SchulzDijkstra/
Abstract:
Traffic information systems are among the most prominent real-world
applications of Dijkstra's algorithm for shortest paths.
We consider the scenario of a central information server in the realm
of public railroad transport on wide-area networks.
Such a system has to process a large number of on-line queries in real time.
In practice, this problem is usually solved by heuristic variations
of Dijkstra's algorithm, which do not guarantee optimality. We report
results from a pilot study, in which we focused on the travel time
as the only optimization criterion. In this study, various
optimality-preserving speed-up techniques for Dijkstra's algorithm
were analysed empirically. This analysis was based on the timetable
data of all German trains and on a ``snapshot'' of half a million
customer queries.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated October 11, 2001, by editor@jea.acm.org