Análise e Comparação dos Algoritmos de Dijkstra e A-Estrela na Descoberta de Caminhos Mínimos em Mapas de Grade

• Marcel L. Rios IFRO / UFAM
• Francisco S. S. Neto UFAM
• José F. Magalhães Netto UFAM

DOI: https://doi.org/10.5753/etc.2016.9852

Abstract

This paper presents a comparison between two algorithms for finding shortest paths in grid maps. First of them is Dijkstra, a well known greedy algorithm for finding the shortest path between vertex in a given graph. And the second one is A* (A-star), an algorithm that uses heuristics to predict their behavior, also for going through a graph and finding the shortest path between vertex. For each algorithm a stop condition has been added, showing their pseudocode, analyzing their complexity and showing promising results of A-Star compared to Dijkstra.

 

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition.

Djojo, M. and Karyono, K. (2013). Computational load analysis of dijkstra, a*, and floyd-warshall algorithms in mesh network. In Robotics, Biomimetics, and Intelligent Computational Systems (ROBIONETICS), 2013 IEEE International Conference on, pages 104–108.

Eraghi, N., Lopez-Colino, F., de Castro, A., and Garrido, J. (2014). Path length comparison in grid maps of planning algorithms: Hctnav, a*; and dijkstra. In Design of Circuits and Integrated Circuits (DCIS), 2014 Conference on, pages 1–6.

Russell, S. J. and Norvig, P. (2013). Artificial Intelligence: A Modern Approach. Pearson Education, 2 edition.