Relatório sobre o Algoritmo Dijkstra

[Não esquece de alterar de DTL pra DTC no cabeçalho do relatório]

Abstract: The problem analyzed in question is the shortest paths problem, many researchers study this problem for a long time and it consists in finding the least-cost path from one vertex to all other vertices in a graph. It is of great importance in many areas of science such as in the field of combinatorial optimization. Several real-world problems can be modeled in this way, as the problem of the shortest route between two cities and the transmission of data in a computer network.

In 1959, a Dutch scientist named Edsger Dijkstra published his work about the solution to this problem: the solution was Dijkstra's algorithm. This algorithm is similar to Breadth-first Search, but it uses a greedy strategy, which is to make decisions based on the information available in the current iteration and solves the shortest path problem only for directed graphs with unbounded non-negative weights.

Thus, as in all study areas of algorithms, it is also sought a solution to the shortest path problem with short computational time implementation, for this reason, since it was designed by Edsger Dijkstra , increasingly sophisticated data structures have been used to minimize its running time (like the Heap data structure and Fibonacci Heap). This work is intended as a basis for discussion on what are the pros and cons of Dijkstra's algorithm from information on how it works, its proof of correctness, the study of its complexity in each case and the algorithm behavior in experiments with several instances of different sizes.

Resumo: O problema analisado em questão é o problema dos caminhos mínimos, este problema é estudado por muitos pesquisadores há muito tempo e consiste em encontrar o caminho de menor custo de um vértice origem a todos os outros vértices de um grafo. É de grande importâncias para muitas áreas da ciência como por exemplo, na área da otimização combinatória. Diversos problemas do mundo real podem ser modelados desta forma, como o problema do percurso mais curto entre duas cidades e a transmissão de dados em uma rede de computadores.

Em 1959, um cientista holandês chamado Edsger Dijkstra publicou seu trabalho a respeito da solução para este problema: a solução era o algoritmo de Dijkstra. Este algoritmo é similar a busca em largura, porém utiliza uma estratégia gulosa, que consiste em tomar decisões com base nas informações disponíveis na iteração corrente e soluciona o problema do caminho mínimo somente para grafos dirigidos com arestas de peso não negativo.

Assim como em todas as áreas do estudo de algoritmos, é buscada uma solução para o problema do caminho mínimo com tempo de execução computacional curto, por esta razão, desde que foi concebido por Edsger Dijkstra, estruturas de dados cada vez mais sofisticadas vêm sendo utilizadas para minimizar seu tempo de execução (como a estrutura Heap e a Heap de Fibonacci).

O trabalho visa servir de base de análise sobre quais são os prós e contras do algoritmo de Dijkstra a partir de informações sobre como o mesmo funciona, sua prova de corretude, o estudo de sua complexidade em cada caso e o comportamento do algoritmo em experimentos com diversas instâncias de tamanhos diferentes.

1. Introdução

        Na área da computação, um problema com uma grande área de abrangência e aplicação é o problema dos caminhos mínimos. Existem diversos motivos para que este problema seja solucionado de forma eficiente e com poucos gastos de recursos computacionais, como por exemplo a transmissão de dados em uma rede de computadores, reconhecimento de voz, segmentação de imagens entre outros.

Por esta razão, foram surgindo com o tempo diversos algoritmos para solucionar o problema dos caminhos mínimos, cada um suas características, aplicações e limitações. Existem métodos simples como a busca em largura, que serve para resolver o problema do caminho mínimo em grafos de pesos unitários não negativos e existem alguns mais sofisticados. Um destes métodos mais eficientes é o algoritmo de Dijkstra (utilizado em grafos com arestas de pesos não negativos), concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959[Ele disse que tinha que referenciar esses anos aí], é bastante utilizado e considerado como um dos mais eficientes métodos existentes.

É um algoritmo guloso, ou seja, que toma decisões com base nas informações disponíveis na iteração corrente. Parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa.

1. Problema e Motivação

Dado um grafo de entrada, nosso objetivo é, a partir de qualquer vértice, encontrar o caminho mínimo deste até todos os outros, apresentando esta informação por meio da árvore de caminhos mínimos.

Nossa motivação é utilizar um algoritmo que resolva o problema do menor caminho, de forma rápida e eficiente e que tenha muitas áreas em que o mesmo possa ser aplicado.

1. Objetivo

Realizar uma análise bem profunda do algoritmo de Dijkstra a partir do estudo de sua implementação, da sua prova de corretude, da análise de sua complexidade e uma avaliação empírica do mesmo com instâncias de diferentes tamanhos, para assim termos informações precisas a respeito de como funciona e sabermos o exato comportamento do algoritmo para diferentes tipos de grafos.

1. Proposta

Aproveitar bem a estratégia gulosa do Dijkstra para facilitar a procura por uma resposta ao problema dos caminhos mínimos.

1. O algoritmo de Dijkstra

O algoritmo funciona da seguinte forma: é tomado um vértice qualquer do grafo como raiz da busca, a distância deste vértice é tomada como zero e dos demais vértices é tomada como infinito e partir desse momento inicial, eles não possuem predecessores. Depois de todas as inicializações necessárias, o vértice tomado como origem visita seus vizinhos e executa a operação da relaxação que consiste na seguinte estratégia: somar o valor agregado ao vértice atual ao valor do peso da aresta na direção do caminho a se seguir, caso o resultado seja menor que o valor agregado ao vértice destino, este é substituído por essa soma, caso contrário, permanece como está. Assim que os vértice origem visita e relaxa seus vizinhos, chega a hora dos seus vizinhos fazerem o mesmo, porém é preciso uma política de escolha sobre qual vértice irá visitar e possivelmente relaxar seus vizinhos, por essa razão no algoritmo de Dijkstra é utilizada uma fila de prioridades para escolha do próximo vértice. Esta fila de prioridades pode ser uma fila simples, uma Heap ou uma Heap de Fibonacci. Ao fim da execução do algoritmo, com as informações dos predecessores de cada vértice é construída a árvore de caminhos mínimos que diz qual o caminho do vértice origem até todos os outros do grafo.
[Tira depois essas paradas aí de algoritmo [pic 1][pic 2]