Estudo comparativo de algoritmos de busca com menor caminho em grafos

Estudo comparativo de algoritmos de busca com menor caminho em grafos

Resumo - O problema de caminho mínimo em grafos é um importante problema da programação matemática, visto que possui aplicações nas mais diversas áreas da Computação e da Engenharia, como: redes de computadores, telecomunicações, transportes, dispositivos de localização, manufaturas, dentre outros. Porém, devido à sua alta complexidade computacional poucos são os algoritmos existentes na literatura.

Entende-se por distância entre s e t ao longo de um caminho que vai do primeiro vértice para o segundo, como sendo o número de veértices que compôem esse caminho. A distância mínima entre dois vértices é a menor das distâncias obtidas de entre os vários caminhos que podem existir entre s e t.

I. INTRODUÇÃO
Desenvolvimento do trabalho a partir das análises de performance na busca do menor caminho, destacando os algoritmos de Dijkstra, Bellman-Ford, Algortimo A* (com heurísticas da distância de Chebyshev, Euclidiana, Mahalanobis, Manhattan e Angular entre 2 vetores). Neste trabalho executamos cada algoritmo acima citado com uma massa de grafos regulares do tipo grade onde haverá apenas a mudança no número de vértices, por exemplo, o arquivo Grafo_04.txt possuirá 4 vértices, o arquivo Grafo_16.txt possuirá 16 vértices, e assim sucessivamente. Executamos 10 (dez) vezes cada algoritmo para todos os grafos e medimos o tempo (em segundos) para cada execução, extraindo após este procedimento a média e o desvio padrão.

II. ALGORITMOS DE BUSCA DE MENOR CAMINHO
A. Algoritmo Dijskstra
O algoritmo de Dijkstra foi desenvolvido por Edsger Wybe Dijkstra em 1959. Este algoritmo tem por função encontrar o caminho mais curto entre duas arestas dentro de um grafo. Para definição deste caminho mínimo é necessário que cada aresta possua um peso positivo, ou seja, cada aresta deve possuir uma métrica para que o algoritmo possa encontrar um caminho onde a soma dos pesos das arestas seja o mais baixo entre