Estudo do Problema do Caminho Mínimo em Grafos

Abstract

Este trabalho visa investigar o problema do caminho mínimo, um tema amplamente reconhecido na teoria dos grafos, com várias aplicações tanto acadêmicas quanto em situações práticas do dia a dia. A Teoria dos Grafos é uma disciplina matemática que se dedica ao estudo de conjuntos de elementos conhecidos como nós ou vértices, bem como das conexões entre eles, chamadas arestas. Cada um desses conjuntos é classificado como um grafo. No presente estudo, foi criada uma biblioteca de grafos com o intuito de gerar e manipular grafos, incluindo seus nós e arestas. Além disso, foram implementados dois algoritmos frequentemente utilizados para resolver o problema do caminho mínimo: o algoritmo de Dijkstra e o algoritmo de Floyd-Warshall, que serviram como objetos de análise. Todas as implementações foram realizadas em C#. A biblioteca desenvolvida funcionou como uma ferramenta para testar os algoritmos implementados, onde também foram executados algoritmos criados manualmente para verificar se cada implementação apresentava os resultados esperados.