Caminho Mı́nimo: Algoritmo Dijikstra Geovani Silva Celebrim1, Juliane Marinho da Silva2, Luı́s Paulo Cavalcante3, Orientador: Leandro G. M. Alvim4 1Departamento de Ciência da Computação – Universidade Federal Rural do Rio de Janeiro (UFRRJ) R. Governador Roberto Silveira S/N – Nova Iguaçu – Rio de Janeiro – RJ – Brasil
[email protected],
[email protected],
[email protected] Abstract. Throughout this article, it is been done an analyses of Dijkstra algo- rithm and its efficiency on solving the shortest path problem. Computational tests were made in order to verify the execution of the algorithm and its effici- ency with graphs with distinct numbers of vertex and weights. At the end it is done a analyses of the obtained results and a conclusion. Resumo. Ao longo deste artigo é realizada uma análise do algoritmo de Dijks- tra e sua eficácia na resolução do problema do caminho mı́nimo. Testes compu- tacionais foram realizados a fim de se verificar a execução do algoritmo e sua eficiência com grafos de diferentes números de arestas e pesos. Ao final é feita uma análise dos resultados obtidos e uma conclusão. 1. Introdução Um dos principais problemas que a Ciência da Computação propõe-se a resolver é o problema do Caminho Mı́nimo. Este problema consiste em encontrar, dado um grafo, o menor caminho de um vértice a todos os outros. Possuindo aplicações em diversos problemas que ocorrem nas áreas de transporte,logı́stica, redes de computadores e de telecomunicações entre outros. Um dos algoritmos propostos pela Ciência da Computação para resolver este pro- blema é o Algoritmo de Dijkstra.Desenvolvido pelo Cientista da Computação Edsger Dijkstra em 1956 e publicado em 1959, este algoritmo soluciona o problema do cami- nho mı́nimo em um grafo valorado direcionado G = (V,E) para o caso de todas as suas arestas possuı́rem pesos não negativos. Neste artigo será discutida a eficiência do algoritmo através do teste de corretude, análise algorı́tmica e testes computacionais realizados com diferentes tipos de grafos. Na seção 2, será feita uma breve descrição do problema. Na seção 3, descreveremos o obje- tivo do problema. Na seção 4, apresentaremos o algoritmo, a demonstração da corretude e a análise de sua complexidade. Na seção 5, são apresentados testes computacionais a fim de demonstrar seu custo com diferentes tipos de grafo. Por fim, na seção 6, será feita uma pequena análise dos resultados obtidos na seção anterior. 2. Problema e Motivação Encontrar a rota mais curta possı́vel do Rio de Janeiro a São Paulo[Cormen 2002].Calcular caminho mais curto entre cidades com o Dijikstra é calcular a distância de grafos com pesos sempre maior que zero. O problema do caminho mı́nimo consiste em encontrar um caminho entre dois vértices u e v em um grafo direcionado e valorado cuja soma dos pesos das arestas seja mı́nimo. Este problema poderia ser resolvido utilizando o algoritmo de Busca em Largura. Contudo, este método não assegura que, no caso de um grafo com arestas de peso diferente de 1, o caminho entre dois vértices seja o mı́nimo. Para tanto, é necessário, pois, um mecanismo que garanta que, a cada vértice visitado, a soma das distâncias dos vértices predecessores a este seja a menor possı́vel. 3. Objetivo O trabalho visa a implementação do algoritmo Dijkstra utilizando heap como fila de pri- oridade para encontrar o caminho mı́nimo com custo computacional baixo e também visa obter resultados para diferentes tipos de entrada para o algoritmo. 4. Proposta 4.1. O Algoritmo de Dijkstra Como fora dito na introdução deste arquivo, o algoritmo de Dijkstra resolve o problema do caminho mı́nimo em um grafo G = (V,E) para o caso de suas arestas possuı́rem pesos não negativos. Com uma boa implementação, o tempo de execução do algoritmo de Dijkstra é menor do que uma outra alternativa para o problema:o algoritmo de Bellmond- Ford. O algoritmo mantém um conjunto S de vértices cujos pesos do caminho mı́nimo final a partir da aresta s já está determinado. Repetitivamente, o algoritmo seleciona um vértice u em V −S com o menor caminho mı́nimo esperado, adiciona u ∈ V −S, e relaxa todos os vértices que partem de u. Para a implementação estudada neste artigo, utilizou- se uma fila de prioridades (heap) Q. Abaixo, o algoritmo em pseudocódigo, sendo w o peso da aresta, s, a aresta inicial, d, a soma das distâncias dos vértices predecessores e π o predecessor do vértice em questão: Dijkstra(G,w, s) 1. para cada vértice v ∈ G.V 2. v.d =∞ 3. v.π = NIL 4. s.d = 0 5. S = ∅ 6. Q = G.V 7. enquanto Q 6= ∅ 8. u = extrairMin{Q} 9. S = S ∪ {u} 10. para cada vertice v ∈ G.adj[u] 11. relaxar(u, v, w) 4.2. Prova de Corretude Dado um grafo G = (V,E), uma função custo c e um vértice s o algoritmo Dijkstra correta- mente encontra uma caminho de custo mı́nimo de s a t para todo vértice acessı́vel a partir de s. Demonstração:Como Q é vazio no final do processo, vale que todos os vértices, e portanto todas as arestas, foram examinadas, o que garante que a função y é um c- potencial. Se y(t) ¡ nC + 1 então o valor y(t) foi atualizado ao menos uma vez, e assim vale que w(t) é diferente de NIL. Logo, segue que existe um st-caminho P no grafo de predecessores e P é um caminho de custo mı́nimo pela condição de otimalidade porque: y(v) = y(u) + c(uv), para todo uv pertencente a w, tal que c(P) = y(t) - y(s) = y(t). Se y(t) = nC + 1, temos que y(t) - y(s) = nC + 1 e da condição de inexistência, concluı́mos que não existe caminho de s a t no grafo. Sendo assim, o algoritmo está correto. 4.3. Análise de sua Complexidade A Construção do heap é O(n), achar o mı́nimo é (log n) que é executado n vezes totali- zando: O(n log n). Refazer o heap tem complexidade (log n) que é executado m vezes no total de O(m log n).A complexidade total é O((n + m)log n) = O(m log n). 5. Experimentos Para avaliar a execução do algoritmo, testes computacionais foram realizados. Os testes apresentados aqui foram realizados em um computador HP G56 Celeron 2,20GHz, 3,00GB, Windows 7 Home Premium 64bits. A metodologia usada foi através de iterações. O número de arestas e vértices que compõem o grafo são dados como parâmetros de entrada. As arestas e seus respectivos pesos foram gerados aleatoriamente através de um gerador de grafos. Os resultados obtidos em cada execução são apresentados na tabela abaixo. Os dados apresentados são, respectivamente, o número de vértices, o número de arestas e o tempo de execução .Este último descreve somente o tempo de execução do algoritmo de Dijkstra. O tempo para geração dos grafos não foi computado. Tabela 1. Tabela de Experimentos Teste Vértices Arestas Tempo (em segundos) 1 5 10 0,015 2 20 50 0,016 3 50 100 0,047 4 100 1000 0,484 5 500 10000 1,716 6 700 25000 3,307 7 750 50000 6,911 6. Conclusões Conforme proposto a busca por um caminho mı́nimo foi abordada neste trabalho e como solução foi aplicado o algoritmo Dijikstra implementando com fila de prioridade para ob- ter uma complexidade ótima.Constatamos então através dos exemperimentos que a união do algoritmo e fila de prioridade geram as vantagens desejadas com custo computacional baixo. O problema do caminho mı́nimo foi resolvido através do uso do algoritmo de Dijkstra .Para um melhor desempenho em sua implementação foi utilizada uma fila de prioridades (heap) para que, fosse possı́vel, manter os vértices ordenados de forma que o algoritmo pudesse ser executado como esperado. Os grafos utilizados nos experi- mentos apresentados anteriormente foram produzidos por um gerador que recebe como parâmetros de entrada o número de vértices e o número de arestas. Os resultados obtidos evidenciam que o algoritmo de Dijkstra é bastante eficaz encontrando a solução com tempo de execução ótimo mesmo para grafos com número de vértices e de arestas elevados, como foi o caso do experimento 7, onde haviam 750 vértices e 50000 arestas. Com isto concluı́mos que para grafos grandes e completos al- goritmo de Dijsktra se mostrou eficiente na resolução do problema do caminho mı́nimo desde que o grafo em questão possua arestas de pesos positivos. O trabalho contribuiu para a aplicação do conteúdo teórico aprendido ao longo do curso e para a melhora na dinâmica em grupo.E também pode ser constatado que de fato mudanças no algoritmo como implementação com fila de prioridade faz a diiferença que contribuiu para gerar resultados ótimos mesmo para um grafo de entrada grande. Mudanças no código podem contribuir para gerar um algoritmo de roteamento usado na área de Redes de Computadores. O objetivo é determinar o melhor caminho entre dois sistemas finais visando melhorar o preenchimento das tabelas de repasses. As mensagens são enviadas pelos roteadores para o sistema final em complexidade linear. Referências Cormen, T. H. e. a. (2002). Algoritmos teoria e prática. Elsevier ltda, 2 edition. [1]Cromen, Thomas H. et al. Introduction to Algorithms. 3th ed. The MIT Press.2009 [2] http://en.wikipedia.org/wiki/Dijkstra