Record:   Prev Next
作者 Ortega-Arranz, Hector., author
書名 The shortest-path problem : analysis and comparison of methods / Hector Ortega-Arranz, Diego R. Llanos, and Arturo Gonzalez-Escribano
出版項 San Rafael, California (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, 2015
國際標準書號 9781627055406 e-book
9781627055390 print
國際標準號碼 10.2200/S00618ED1V01Y201412TCS001 doi
book jacket
說明 1 online resource (xv, 71 pages) : illustrations
text rdacontent
electronic isbdmedia
online resource rdacarrier
系列 Synthesis lectures on theoretical computer science ; # 1
Synthesis digital library of engineering and computer science
Synthesis lectures on theoretical computer science ; # 1
附註 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
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
Title from PDF title page (viewed on December 23, 2014)
鏈接 Print version: 9781627055390
主題 Graph algorithms
Paths and cycles (Graph theory)
graph algorithms
graph search
shortest-path problem
Dijkstra's algorith
A* algorithm
highway hierarchies
contraction hierarchies
transit-node routing
hub-based labeling algorithm
landmark A*
edge flags
reach-based routing
precomputed cluster distances
Alt Author Llanos, Diego R., author
Gonzalez-Escribano, Arturo., author
Record:   Prev Next