Central Library

Normal view MARC view ISBD view

The Shortest-Path Problem [electronic resource] : Analysis and Comparison of Methods / by Arturo Gonzalez-Escribano, Diego R. Llanos, Hector Ortega-Arranz.

By: Gonzalez-Escribano, Arturo [author.].
Contributor(s): Llanos, Diego R [author.] | Ortega-Arranz, Hector [author.] | SpringerLink (Online service).
Material type: materialTypeLabelBookSeries: Synthesis Lectures on Theoretical Computer Science: Publisher: Cham : Springer International Publishing : Imprint: Springer, 2015Edition: 1st ed. 2015.Description: XV, 71 p. online resource.Content type: text Media type: computer Carrier type: online resourceISBN: 9783031025747.Subject(s): Mathematics | Computer science | Graph theory | Artificial intelligence | Biomathematics | Mathematics | Theory of Computation | Graph Theory | Artificial Intelligence | Mathematical and Computational BiologyAdditional physical formats: Printed edition:: No title; Printed edition:: No titleDDC classification: 510 Online resources: Click here to access online
Contents:
List of Figures -- List of Tables -- Acknowledgments -- Introduction -- Graph Theory Basics -- Classical Algorithms -- Hierarchical Preprocessing-Dependent Approaches -- Non-Hierarchical Preprocessing-Dependent Approaches -- Analysis and Comparison of Approaches -- Conclusions -- Bibliography -- Authors' Biographies .
In: Springer Nature eBookSummary: 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. Table of Contents: List of Figures / List of Tables / Acknowledgments / Introduction / Graph Theory Basics / Classical Algorithms / Hierarchical Preprocessing-Dependent Approaches / Non-Hierarchical Preprocessing-Dependent Approaches / Analysis and Comparison of Approaches / Conclusions / Bibliography / Authors' Biographies.
    average rating: 0.0 (0 votes)
No physical items for this record

List of Figures -- List of Tables -- Acknowledgments -- Introduction -- Graph Theory Basics -- Classical Algorithms -- Hierarchical Preprocessing-Dependent Approaches -- Non-Hierarchical Preprocessing-Dependent Approaches -- Analysis and Comparison of Approaches -- Conclusions -- Bibliography -- Authors' Biographies .

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. Table of Contents: List of Figures / List of Tables / Acknowledgments / Introduction / Graph Theory Basics / Classical Algorithms / Hierarchical Preprocessing-Dependent Approaches / Non-Hierarchical Preprocessing-Dependent Approaches / Analysis and Comparison of Approaches / Conclusions / Bibliography / Authors' Biographies.

There are no comments for this item.

Log in to your account to post a comment.