Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Includes bibliographical references (pages 63-69).

1. Introduction --

2. Graph theory basics -- 2.1 Definitions -- 2.2 A study case --

3. Classical algorithms -- 3.1 Dijkstra's algorithm -- 3.1.1 Using priority queues -- 3.1.2 Case study -- 3.2 Bidirectional search -- 3.2.1 Case study -- 3.3 Goal-directed A* search -- 3.3.1 Case study -- 3.4 Bidirectional A* search -- 3.4.1 Case study --

4. Hierarchical preprocessing-dependent approaches -- 4.1 Highway hierarchies -- 4.1.1 Preprocessing: building the highway network -- 4.1.2 Query -- 4.1.3 Optimizations -- 4.1.4 Case study -- 4.2 Optimizing hierarchical queries with distance tables -- 4.3 Contraction hierarchies -- 4.3.1 Preprocessing: contracting the network -- 4.3.2 Preprocessing: choosing the best ordering -- 4.3.3 Preprocessing: blending the ordering process and the network contraction -- 4.3.4 Query -- 4.3.5 Case study -- 4.4 Transit-node routing -- 4.4.1 Transit-node set selection -- 4.4.2 Preprocessing -- 4.4.3 Query -- 4.4.4 Economic variant -- 4.4.5 Case study -- 4.5 Hub-based labeling algorithm -- 4.5.1 Distance labeling -- 4.5.2 Preprocessing: computing labels -- 4.5.3 Query -- 4.5.4 Case study -- 4.6 Other hierarchical preprocessing methods --

5. Non-hierarchical preprocessing-dependent approaches -- 5.1 Landmark A* -- 5.1.1 Landmark selection -- 5.1.2 Preprocessing: computing landmark distances -- 5.1.3 Query -- 5.1.4 Case study -- 5.2 Edge flags -- 5.2.1 Region definition -- 5.2.2 Preprocessing: raising flags -- 5.2.3 Query -- 5.2.4 Case study -- 5.3 Reach-based routing -- 5.3.1 Preprocessing: computing reach values -- 5.3.2 Query -- 5.3.3 Case study -- 5.4 Precomputed cluster distances -- 5.4.1 Partitioning -- 5.4.2 Preprocessing: computing upper and lower bounds -- 5.4.3 Query -- 5.4.4 Case study -- 5.5 Other non-hierarchical preprocessing methods -- 5.6 Combining hierarchical with non-hierarchical methods --

6. Analysis and comparison of approaches -- 6.1 Quantitative search space analysis -- 6.1.1 Dijkstra's algorithm -- 6.1.2 Bidirectional Dijkstra's algorithm -- 6.1.3 A* algorithm -- 6.1.4 Trends and comparisons -- 6.2 Qualitative search space analysis -- 6.2.1 Lessons from our case study -- 6.2.2 Uniform search space comparison --

7. Conclusions -- Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

Many applications in different domains need to calculate the shortest-path between two points in a graph. In this paper we describe this shortest path problem in detail, starting with the classic Dijkstra's algorithm and moving to more advanced solutions that are currently applied to road network routing, including the use of heuristics and precomputation techniques. Since several of these improvements involve subtle changes to the search space, it may be difficult to appreciate their benefits in terms of time or space requirements. To make methods more comprehensive and to facilitate their comparison, this book presents a single case study that serves as a common benchmark. The paper also compares the search spaces explored by the methods described, both from a quantitative and qualitative point of view, and including an analysis of the number of reached and settled nodes by different methods for a particular topology.

Also available in print.

Title from PDF title page (viewed on December 23, 2014).