The Shortest-Path Problem

The Shortest-Path Problem
Analysis and Comparison of Methods

Hector Ortega-Arranz, Diego R. Llanos, Arturo Gonzalez-Escribano
ISBN: 9781627055390 | PDF ISBN: 9781627055406
Copyright © 2015 | 87 Pages | Publication Date: 12/01/2014

BEFORE YOU ORDER: You may have Academic or Corporate access to this title. Click here to find out: 10.2200/S00618ED1V01Y201412TCS001

Ordering Options: Paperback $30.00   E-book $24.00   Paperback & E-book Combo $37.50


Why pay full price? Members receive 15% off all orders.
Learn More Here

Read Our Digital Content License Agreement (pop-up)

Purchasing Options:



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

About the Author(s)

Hector Ortega-Arranz, Universidad de Valladolid, Spain
Hector Ortega-Arranz received his M.S. in Computer Science Engineering, and his M.S. in Research in Information and Communication Technologies, from the Universidad de Valladolid, Spain, in 2010 and 2011, respectively. He is currently a researcher and a Ph.D. candidate in the Department of Computer Science of this university. His research interests include shortest-path algorithms, parallel and distributed computing, and GPU computing.

Diego R. Llanos, Universidad de Valladolid, Spain
Diego R. Llanos received his M.S. and Ph.D. degrees in Computer Science from the Universidad de Valladolid, Spain, in 1996 and 2000, respectively. He is a recipient of the Spanish government's
national award for academic excellence. Dr. Llanos is Associate Professor of Computer Architecture at the Universidad de Valladolid, and his research interests include parallel and distributed computing, automatic parallelization of sequential code, and embedded computing. He is a Senior Member of the IEEE and Senior Member of the ACM.

Arturo Gonzalez-Escribano, Universidad de Valladolid, Spain
Arturo Gonzalez-Escribano received his M.S. and Ph.D. degrees in Computer Science from the Universidad de Valladolid, Spain, in 1996 and 2003, respectively. Dr. Gonzalez-Escribano is
Associate Professor of Computer Science at the Universidad de Valladolid, and his research interests include parallel and distributed computing, parallel programming models, and embedded
computing. He is a Member of the IEEE Computer Society and Member of the ACM.

Reviews

Customers who bought this product also purchased
Reasoning with Probabilistic and Deterministic Graphical Models
Reasoning with Probabilistic and Deterministic Graphical Models
Browse by Subject
Case Studies in Engineering
ACM Books
IOP Concise Physics
SEM Books
0 items
LATEST NEWS

Newsletter
Note: Registered customers go to: Your Account to subscribe.

E-Mail Address:

Your Name: