Búsquedas de caminos mínimos haciendo uso de grafos reducidos.

One of the widely studied ptimization problems consistsin finding shortest paths from a source to a destination. Classical algorithms for solving this problemare not scalable. Several approaches have been proposed, using heuristics, to reduce the run time. These approaches introduce anerrorand, consequently, they do not guaranteean optimum value inall cases. In this paper we propose agraph reduction algorithm without loss of information, which helps to reduce the run time of algorithms. In addition, we propose a modification to the Dijkstraalgorithmto be used on reduced graphs, guaranteeing an optimal result in all cases. Besides, a comparison between the run time of the proposed algorithms and Dijkstraand A* algorithms is presented. This comparison shows that it ispossible to obtain an optimal pathin a similar time, and even in less time, than those obtained by heuristic algorithms. [ABSTRACT FROM AUTHOR]