Discrete Mathematics and Theoretical Computer Science

TITLE: "The Shortest Path Problem"

EDITORS: Camil Demetrescu, Andrew V. Goldberg, David S. Johnson

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:

- Definition of common file formats for several variants of the shortest path problem, both static and dynamic. These comprised extensions of the famous DIMACS graph file format used by several algorithmic software libraries.
- Definition of a common set of core input instances for evaluating shortest path algorithms.
- Definition of benchmark codes for shortest path problems.
- Design of new shortest path algorithms.
- Experimental evaluation of state of the art implementations of shortest path codes on the core input families.
- A discussion of directions for further research in the area of shortest paths, identifying problems critical in real-world applications for which efficient solutions still remain unknown.

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

Contacting the Center

Document last modified on August 12, 2009.