LEADER 00000nam  2200757 i 4500 
001    7005382 
003    IEEE 
005    20141224145217.0 
006    m    eo  d         
007    cr cn |||m|||a 
008    141223s2015    caua   foab   000 0 eng d 
020    9781627055406|qe-book 
020    |z9781627055390|qprint 
024 7  10.2200/S00618ED1V01Y201412TCS001|2doi 
035    (OCoLC)898747111 
040    CaBNVSL|beng|erda|cCaBNVSL|dCaBNVSL|dAS|dIIS 
050  4 QA166.245|b.O788 2015 
082 04 511.5|223 
100 1  Ortega-Arranz, Hector.,|eauthor 
245 14 The shortest-path problem :|banalysis and comparison of 
       methods /|cHector Ortega-Arranz, Diego R. Llanos, and 
       Arturo Gonzalez-Escribano 
264  1 San Rafael, California (1537 Fourth Street, San Rafael, CA
       94901 USA) :|bMorgan & Claypool,|c2015 
300    1 online resource (xv, 71 pages) :|billustrations 
336    text|2rdacontent 
337    electronic|2isbdmedia 
338    online resource|2rdacarrier 
490 1  Synthesis lectures on theoretical computer science ;|v# 1 
500    Part of: Synthesis digital library of engineering and 
       computer science 
504    Includes bibliographical references (pages 63-69) 
505 0  1. Introduction -- 
505 8  2. Graph theory basics -- 2.1 Definitions -- 2.2 A study 
       case -- 
505 8  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 -- 
505 8  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
       -- 
505 8  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 -- 
505 8  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 --
505 8  7. Conclusions -- Bibliography -- Authors' biographies 
506    Abstract freely available; full-text restricted to 
       subscribers or individual document purchasers 
510 0  Compendex 
510 0  INSPEC 
510 0  Google scholar 
510 0  Google book search 
520 3  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 
530    Also available in print 
538    Mode of access: World Wide Web 
538    System requirements: Adobe Acrobat Reader 
588    Title from PDF title page (viewed on December 23, 2014) 
650  0 Graph algorithms 
650  0 Paths and cycles (Graph theory) 
653    graph algorithms 
653    graph search 
653    shortest-path problem 
653    Dijkstra's algorith 
653    A* algorithm 
653    highway hierarchies 
653    contraction hierarchies 
653    transit-node routing 
653    hub-based labeling algorithm 
653    landmark A* 
653    edge flags 
653    reach-based routing 
653    precomputed cluster distances 
700 1  Llanos, Diego R.,|eauthor 
700 1  Gonzalez-Escribano, Arturo.,|eauthor 
776 08 |iPrint version:|z9781627055390 
830  0 Synthesis digital library of engineering and computer 
       science 
830  0 Synthesis lectures on theoretical computer science ;|v# 1 
856 41 |zeBook(IEEE-MORGAN)|uhttp://ieeexplore.ieee.org/servlet/
       opac?bknumber=7005382