Análise e aplicação dos algoritmos de Dijkstra e Gale Shapley: uma abordagem teórica e prática

Abstract

RESUMO: Este trabalho apresenta uma análise teórica e prática dos grafos, com foco nos algoritmos de Dijkstra e Gale-Shapley. A pesquisa inicia-se com uma revisão bibliográfica sobre o contexto histórico dos grafos, destacando a relevância desses algoritmos em áreas como otimização de rotas e alocação de recursos. O algoritmo de Dijkstra foi aplicado em um cenário de otimização de caminhos mínimos em redes de transporte, enquanto o algoritmo de Gale-Shapley foi utilizado para resolver problemas de emparelhamento estável, como a alocação de vagas. As implementações foram realizadas utilizando Python e bibliotecas especializadas. Os resultados confirmam a eficácia dos algoritmos em suas respectivas áreas de aplicação, ressaltando também as limitações em cenários de maior complexidade. O estudo conclui sugerindo a ampliação da análise para casos mais dinâmicos e a aplicação dos algoritmos em contextos emergentes, como redes adaptativas e sistemas distribuídos.___ABSTRACT: This work presents a theoretical and practical analysis of graphs, focusing on the Dijkstra and Gale-Shapley algorithms. The research begins with a literature review on the historical context of graphs, highlighting the relevance of these algorithms in areas such as route optimization and resource allocation. Dijkstra's algorithm was applied in a shortest path optimization scenario in transportation networks, while the Gale-Shapley algorithm was used to solve stable matching problems, such as slot allocation. The implementations were carried out using Python and specialized libraries. The results confirm the effectiveness of the algorithms in their respective areas of application, also highlighting the limitations in more complex scenarios. The study concludes by suggesting the expansion of the analysis to more dynamic cases and the application of algorithms in emerging contexts, such as adaptive networks and distributed systems.