CAMINHO MÍNIMO DE REDES CONECTADAS UTILIZANDO GRAFOS

Abstract

Neste trabalho propõe-se desenvolver e implementar modelos matemáticos capazes de descrever o comportamento do caminho mínimo em redes conectadas, aplicando técnicas de otimização em problemas apresentados na literatura e buscando relacionar um problema real que possibilite utilizar os conhecimentos adquiridos. Com esses objetivos, foram implementados e analisados quatro algoritmos encontrados na literatura: de Dijkstra, Ford/More, Floyd, Dantzig. Para validação das técnicas os’ algoritmos foram aplicados à Rede Ipê da RNP para verificar a funcionalidade e definição do caminho ótimo entre os PoPs utilizando o atraso como ponto de decisão. O problema do caminho mínimo está intimamente ligado ao nosso cotidiano, e embora algum algoritmo tenha se mostrado mais eficiente, não devemos nos limitar a ele. Cada algoritmo encaixa-se melhor numa determinada situação.