To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
This volume contains papers arising from the 9th DIMACS Implementation Challenge (http://www.dis.uniroma1.it/~challenge9), which was devoted to shortest path algorithms.
DIMACS implementation Challenges are aimed at narrowing the gap between theory and practice for algorithms in specific problem areas. This is achieved by developing a common infrastructure for experimental algorithm evaluation and encouraging researchers to develop and compare state of the art algorithm implementations. The first Challenge was held in 1990-1991 and was devoted to Network Flows and Matching. Other addressed problems included: Maximum Clique, Graph Coloring, and Satisfiability (1992-1993), Parallel Algorithms for Combinatorial Problems (1993-1994), Fragment Assembly and Genome Rearrangements (1994-1995), Priority Queues, Dictionaries, and Multi-Dimensional Point Sets (1995-1996), Near Neighbor Searches (1998-1999), Semidefinite and Related Optimization Problems (1999-2000), and The Traveling Salesman Problem (2000-2001). Selection of the problem area is the key to a Challenge's success. A good area is one with active theoretical algorithmic research and a lack of the common infrastructure. In 2004, when the call for the Ninth Challenge was issued, this was the case for the area of shortest path algorithms.
Shortest path problems are among the most fundamental combinatorial optimization problems with many applications, both direct and as subroutines. They arise naturally in a remarkable number of real-world settings. A limited list includes transportation planning, network optimization, packet routing, image segmentation, speech recognition, document formatting, robotics, compilers, traffic information systems, and dataflow analysis. Shortest path algorithms have been studied since the 1950's and still remain an active area of research. The goal of the Ninth DIMACS Implementation Challenge was to stimulate research on shortest path algorithms by creating a reproducible picture of the state of the art. The main results of the Challenge included:
The Challenge call for participation was broad, inviting work on most polynomially- solvable variants of shortest paths. The organizers provided input-output file formats and benchmark problem solvers for the most basic problems and indicated that more formats will be developed if needed.
Participants at sites in the U.S. and Europe undertook projects during the period from October 2005 to November 2006, studying several variants of the shortest paths problem. For its relevance in modern applications such as GPS navigation systems, the point-to-point shortest paths problem, which consists of answering multiple online queries about the shortest paths between pairs of vertices, was the most popular problem during the Challenge, attracting about half of the contributions. Other variants under investigation included k-shortest paths and language-constrained shortest paths. Parallel and external memory implementations of shortest paths algorithms were also studied.
In the first stage of the Challenge, the organizers and the participants obtained or developed real-life problems and problem generators, from which benchmark problem families were selected. The participants were encouraged to use these problems whenever practical during the second part of the Challenge, during which algorithm implementations were developed and evaluated. In addition, the participants were free to use any other problems that they found useful in evaluating their algorithm performance.
The Challenge culminated in a workshop held at the DIMACS Center at Rutgers University, Piscataway, New Jersey on November 13-14, 2006. Following the workshop, participants were encouraged to share test instances whenever possible, to rework their implementations and experiments in light of the feedback at the workshop, and to submit a final report for this book. After a careful reviewing process, comparable to that of refereeing for a high-quality journal, twelve full articles were selected for this volume. In view of the practical importance of the problems studied in this Challenge, this volume also contains a survey of applications of shortest path problems.
More than 40 researchers attended the workshop; there were thirteen project presentations, one invited talk, and a panel discussion. The specific application problems presented at the workshop included point-to-point shortest paths, kshortest paths, parallel shortest paths, external-memory BFS, and language-constrained shortest paths. The invited presentation was given by David A. Bader (Georgia Institute of Technology). The lecture focused on solving massive graph problems on large-scale parallel machines and presented several graph theoretic kernels for connectivity and centrality. The lecture discussed how the underlying parallel architectures affects algorithm development, ease of programming, performance, and scalability.
In addition, many participants took part in a special competition held during
the workshop and devoted to the point-to-point shortest path problem. The aim
was to compare the performance and the robustness of the different implementations
discussed at the workshop. The rules of the competition were announced on the first
day of the workshop and the results were due on the second day. The competition
consisted of preprocessing a version of the full road network of continental U.S.
with unit edge lengths and answering a sequence of 1,000 random distance queries. Each participating team used their own machine and computational environment. Note that the U.S. graph with lengths corresponding to travel distances and transit times was a part of the benchmark data set, and the unit length function was a natural "new" length function to consider. Some of the participants' codes were unable to deal with the size of the full U.S. graph, or incurred runtime errors. However, six point-to-point implementations successfully preprocessed the graph and answered the queries. These included two codes, RE and REAL(16, 1), which were not eligible for the official competition because one of the co-authors on the paper was also an organizer. These two codes were run on the problem prior to the competition to ensure that the problem could be solved in 24 hours.
Because results were obtained on different platforms, each participant ran a Dijkstra benchmark code [3] on the USA graph to allow machine calibration. The final ranking was made by considering each query time divided by the time required by the benchmark code on the same platform (benchmark ratio). Other performance measures taken into account were space usage and the average number of nodes scanned by query operations.
The results of the competition are reported in Table 1. All six codes that successfully handed the graph had substantially faster query times than the benchmark Dijkstra code, which did no preprocessing. As one can see from the table, the fastest query time was achieved by the HH-based transit code of Peter Sanders and Dominik Schultes. (The times reported in the table are for the different platforms used by the participants and are not normalized. They are reasonably comparable, however. Based on the benchmark runs, no pair of platforms differed in speed by more than 22%.)
Work done by the participants during the Challenge improved the state of the art in shortest path algorithms. In addition, the infrastructure developed during the Challenge should facilitate further research in the area, leading to substantial follow-up work as well as to better and more uniform experimental standards.
The expert assistance of the DIMACS staff in hosting and arranging the workshop is gratefully acknowledged. We would like to thank Microsoft Research for providing partial funding for the workshop. We also would like to thank all the Challenge participants, whose hard work and enthusiasm was the key to the success of the Challenge.
Camil Demetrescu
Andrew V. Goldberg
David S. Johnson
March 2009
Bibliography
[1] H. Bast, S. Funke, and D. Matijevic, Transit: Ultrafast shortest-path queries with lineartime preprocessing, in 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, November 13-14, 2006.
[2] D. Delling, P. Sanders, D. Schultes, and D. Wagner, Highway hierarchies star, in 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, November 13-14, 2006.
[3] E. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, 1 (1959), pp. 269-271.
[4] A. Goldberg, H. Kaplan, and R. Werneck, Better landmarks within reach, in 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, November 13-14, 2006.
[5] P. Sanders and D. Schultes, Robust, almost constant time shortest-path queries in road networks, in 9th DIMACS Implementation Challenge Workshop: Shortest Paths, DIMACS Center, Piscataway, NJ, November 13-14, 2006.
Foreword vii
Introduction ix
Real-World Applications of Shortest Path Algorithms
Jose L. Santos 1
An Experimental Evaluation of Point-To-Point Shortest
Path Calculation on Road Networks with Precalculated
Edge-Flags
Ulrich Lauther 19
Fast Point-to-Point Shortest Path Computations with
Arc-Flags
Moritz Hilger, Ekkehard Kohler, Rolf H. Mohring, and
Heiko Schilling 41
High-Performance Multi-Level Routing
Daniel Delling, Martin Holzer, Kirill M¨uller,
Frank Schulz, and Dorothea Wagner 73
Reach for A*: Shortest Path Algorithms with Preprocessing
Andrew V. Goldberg, Haim Kaplan, and Renato F.
Werneck 93
Highway Hierarchies Star
Daniel Delling, Peter Sanders, Dominik Schultes,
and Dorothea Wagner 141
Ultrafast Shortest-Path Queries via Transit Nodes
Holger Bast, Stefan Funke, and Domagoj Matijevic 175
Robust, Almost Constant Time Shortest-Path Queries in
Road Networks
Peter Sanders and Dominik Schultes 193
Single-Source Shortest Paths with the Parallel Boost
Graph Library
Nick Edmonds, Alex Breuer, Douglas Gregor, and
Andrew Lumsdaine 219
Parallel Shortest Path Algorithms for Solving Large-
Scale Instances
Kamesh Madduri, David A. Bader, Jonathan W. Berry,
and Joseph R. Crobak 249
Breadth First Search on Massive Graphs
Deepak Ajwani, Ulrich Meyer, and Vitaly Osipov 291
Engineering Label-Constrained Shortest-Path Algorithms
Chris Barrett, Keith Bisset, Martin Holzer, Goran
Konjevod, Madhav Marathe, and Dorothea Wagner 309
Index of Volumes
DIMACS Homepage