GRAFOS: algoritmos para calcular os menores caminhos

Resumo

Grafos são representações subjetivas formadas por dois conjuntos: vértices e arestas, comumente usados para representar situações tais como rodovias entre uma cidade e outra; rede de distribuição de energia elétrica interligando casas. Nesse trabalho apresenta-se uma breve introdução à teoria dos grafos, além de relacionar grafos a matrizes de adjacência e de incidência, com o objetivo principal de apresentar a alunos do Ensino Médio os algoritmos de Dijkstra e de Floyd-Wharshall para encontrar o menor caminho. Para resolução do problema de caminho mínimo existem vários algoritmos, dentre eles vamos destacar os algoritmos de Dijkstra e de Floyd-Warshal. O algoritmo de Dijkstra é uma solução para o problema do caminho mínimo de origem única, funciona em grafos orientados e não orientados, no entanto, todas as arestas devem conter apenas custos positivos. O algoritmo de Floyd funciona em grafos ponderados seja ele orientado ou não orientado, e trabalha com pesos (ou valores) positivos e negativos. Compreender que a interpretação de um problema pode ser transcrita através de uma modelagem antes de encontrar sua solução, nesse caso a utilização de um desenho (grafo) para modelar problemas enriquece o conhecimento do aluno e oferece ferramentas adequadas para tomada de decisões na busca de uma solução, a qual pode ser obtida manualmente ou com o auxílio de um computador com novas oportunidades de aprendizagem até mesmo em outras disciplinas e assuntos que não sejam a Matemática.