The Shortest-Path Problem

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 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 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.

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 .