Vamos estudar um dos maiores clássicos da computação, o algoritmo de caminhos mínimos de Dijkstra. Primeiro, vamos relembrar o algoritmo de busca em largura para cálculo de distâncias, que é generalizado pelo algoritmo de Dijkstra. distancias(grafo G=(V,E), vértice s) { para v \in V marque v como não encontrado dist[v] = +\inf marque s como encontrado dist[s] = 0 seja Q uma fila inicializada com o vértice s enquanto Q != \empty remova um vértice v do início de Q para cada aresta (v, w) se w não foi encontrado marque w como encontrado insira w no final de Q dist[w] = dist[v] + 1 } Para simplificar, vamos supor que todos os vértices do grafo são alcançados a partir do vértice s. Se esse não for o caso, podemos focar nos vértices alcançáveis realizando uma busca a partir de s antes, ou modificando levemente o algoritmo de Dijkstra. Dijkstra(grafo G=(V,E), comprimentos l, vértice s) { para todo v \in V dist[v] = +\inf prev[v] = NULL dist[s] = 0 R = {} enquanto R != V pegar o vértice v em V \ R com menor valor de dist[] // escolha gulosa do algoritmo de Dijkstra adicione v a R para toda aresta (v, w) com w em V \ R se dist[w] > dist[v] + l(v, w) dist[w] = dist[v] + l(v, w) prev[w] = v } Antes de provarmos a corretude deste algoritmos e de tratarmos dos detalhes de implementação e da eficiência do mesmo, vamos considerar suas limitações. Em particular, este algoritmo pode não devolver a solução correta quando as arestas apresentam custo negativo. - Isso ocorre porque a escolha gulosa pode definir uma certa distância para um vértice, sem considerar um caminho que passa por outros vértices, primeiro tendo um custo maior, mas depois tendo seu custo reduzido por conta de arestas de custo negativo. Poderíamos pensar em reduzir o problema com arestas negativas para o problema sem essas arestas. Uma tentativa seria somar o valor absoluto da aresta mais negativa no comprimento de todas as arestas. Isso certamente faria com que o grafo não tivesse mais arestas negativas. - No entanto, o caminho mínimo entre os vértices seria alterado, pois caminhos com diferentes números de arestas seriam afetados de modo distinto. Prova de corretude: O algoritmo de Dijkstra mantém as seguintes propriedades invariantes no início de cada iteração do laço principal do algoritmo: 1 - para todo vértice v em R o valor dist[v] corresponde ao comprimento do caminho mínimo de s até v 2 - para todo vértice v em V o vértice prev[v] corresponde ao penúltimo vértice em um menor caminho de s até v cujos vértices intermediários estão em R 3 - para todo vértice v em V \ R o valor dist[v] corresponde ao comprimento do menor caminho cujos vértices intermediários estão em R Faremos a prova por indução no número de iterações k. Caso base: no início da primeira iteração R é vazio, portanto as propriedades 1 e 2 valem trivialmente e a propriedade 3 vale porque dist[s] = 0 e os demais dist[] são +inf. H.I.: as propriedades 1, 2 e 3 do invariante valem no início da iteração k. Passo: considere a iteração k em que o vértice v é inserido em R. Esse vértice é inserido por ser o vértice fora de R com menor valor para dist[]. Pela propriedade 3 da H.I. temos que v é o vértice com menor caminho cujos vértices intermediários estão em R. Vamos mostrar que este é um menor caminho de s até v. Considere um caminho P qualquer de s até v. Em algum momento P tem que cruzar a fronteira entre vértices que estão em R e vértices fora de R. Suponha que o primeiro vértice de P fora de R é w, e divida P em P1 (parte que vai de s a w) e P2 (parte que vai de w a v). Pela propriedade 3 da H.I. temos que dist[w] é o menor caminho de s até w que só usa vértices em R. Portanto, dist[w] <= custo de P1. Como não temos arestas de custo negativo, custo de P2 >= 0. Portanto, comprimento de P = custo de P1 + custo de P2 >= dist[w] + 0 >= dist[v] pela escolha de v como o vértice que minimiza dist[]. Assim, dist[v] corresponde ao comprimento do caminho mínimo de s até v e a propriedade 1 do invariante se mantém depois que v é adicionado a R (no início da iteração k+1). Agora vamos mostrar que as propriedades 2 e 3 se mantém. Para os vértices cujos valores dist[] e prev[] não mudaram ao longo da iteração k o resultado segue da H.I.. Vamos considerar um vértice z para o qual os valores dist[z] e prev[z] mudaram na iteração k. Neste caso dist[z] = dist[v] + l(v,z) é menor que o valor antigo de dist[z]. Isso significa que dist[z] corresponde ao comprimento do menor caminho cujos vértices intermediários estão em R, já que agora v está em R e o antigo dist[z] satisfazia a propriedade 3 da H.I.. Além disso, a propriedade 2 vale porque prev[z] passa a ser v. Implementação e eficiência: A eficiência do algoritmo de Dijkstra depende fortemente da estrutura de dados que usamos para implementar as operações de escolha do vértice com menor valor de dist[] (e também na qual iremos atualizar os valores de dist[] conforme encontramos novas arestas). A escolha tradicional neste caso, já que estamos fazendo sucessivas operações de remover o mínimo de um conjunto, é utilizar um heap. Um heap de mínimo suporta as operações de remover o mínimo e inserir no heap em tempo O(log n). Também conseguimos construir um heap com n elementos em tempo O(n) e, o que será particularmente relevante para esta aplicação, conseguimos atualizar o valor de elementos no meio do heap em tempo O(log n). - Como implementar essa última operação? Se implementarmos o algoritmo de Dijkstra usando um heap de mínimo ele terá complexidade e pior caso O(m log n) - estamos supondo que o grafo é conexo, por isso o número de arestas supera o número de vértices - essa complexidade vem do fato que em cada iteração do algoritmo um vértice é removido do heap - assim, ao longo de toda a execução as remoções levam tempo O(n log n). - além disso, cada aresta é considerada no máximo duas vezes - uma cada vez que um vértice extremo é removido do heap - no caso desta aresta corresponder a um caminho mais curto do que o já encontrado para o vértice destino - o valor dist[] do vértice destino tem que ser atualizado no heap - atualizar tal valor custa O(log n) - ao longo de toda a execução do algoritmo essas operações custam O(m log n) Para a maior parte dos grafos essa é a escolha para se implementar o algoritmo de Dijsktra, já que ela é quase linear no tamanho do grafo. - No entando, existe uma exceção. No caso de grafos particularmente densos, temos que m = Theta(n^2) - Nestes grafos a complexidade do algoritmo será Theta(m log n) = Theta(n^2 log n) - Será que neste caso conseguimos fazer melhor? - A resposta é sim. Surpreendentemente, neste caso conseguimos melhorar a eficiência de pior caso do algoritmo usando uma estrutura de dados mais simples no lugar do heap. - Considerem usar apenas um vetor de tamanho n para armazenar as informações dist[]. - A desvantagem de usar um vetor é que encontrar o mínimo custa Theta(n), pois temos que percorrer o vetor inteiro. - A vantagem é que atualizar um valor custa O(1), pois conseguimos acessar o valor dist[] de um vértice diretamente. - Assim, cada uma das n remoções de vértice com dist[] mínimo do laço principal do algoritmo custarão Theta(n) - No total, isso custará Theta(n^2) - Por outro lado, cada umas das atualizações de dist[] desencadeadas por encontrar uma nova aresta custarão Theta(1) - No total, isso custará Theta(m) = Theta(n^2), já que estamos falando do caso do grafo muito denso. - Assim, o custo total do algoritmo será Theta(n^2), que é um pouco melhor que Theta(n^2 log n).