5 - BUSCA DE CAMINHO MAIS CURTO

Última revisão: 23/05/2001

Nessa parte do curso vamos estudar duas técnicas para identificar, entre dois vértices de um grafo valorado, o caminho de menor peso. A primeira abordagem utiliza um algoritmo guloso, o algoritmo de Dijkstra, e a segunda utiliza a programação dinâmica.

Algoritmo de Dijkstra

Descrição do algoritmo

O algoritmo de Dijkstra identifica, a partir de um vértice do grafo, qual é o custo mínimo entre esse vértice e todos os outros do grafo. No início, o conjunto S contém somente esse vértice, chamado origem. A cada passo, selecionamos no conjunto de vértices sobrando, o que é o mais perto da origem. Depois atualizamos, para cada vértice sobrando, a sua distância em relação à origem. Se passando pelo novo vértice acrescentado, a distância fica menor, é essa nova distância que será memorizada.

Suponhamos que o grafo é representado por uma matriz de adjacência onde temos o valor se não existe aresta entre dois vértices. Suponhamos também que os vértices do grafo são enumerados de 1 até n, isto é, o conjunto de vértices é N = {1, 2, ..., n}. Utilizaremos também um vetor D[2..n] que conterá a distância que separa todo vértice do vértice 1 (o vertíce do grafo que é o vertice 1 é escolhido arbitrariamente). Eis o algoritmo:

Para entender melhor o algoritmo, considere o grafo direcionado ilustrado na figura 1.

Figura 1

As etapas da execução do algoritmo são as seguintes:

Da maneira que o algoritmo foi apresentado, obtemos o custo do caminho mínimo para qualquer vértices, mas não obtemos o caminho mínimo. Para identificar esse caminho mínimo, é só acrescentar mais um vetor P[2..n], onde P[v] indica o vértice que precede v no caminho mais curto. A modificação do algoritmo para obter esse vetor é simples. Primeiro devemos inicializar esse vetor. Segundo, no mesmo momento que o vetor D é atualizado, atualizamos também o vetor P. O algoritmo modificado é o seguinte:

Com esse algoritmo modificado, as etapes da execução são as seguintes:

Vemos que o estado final do vetor P é [3,1,5,1]. Para saber qual é o caminho mais curto entre os vértices 1 e 2, procuramos o valor na posiçao 2 desse vetor (não esqueça que P e D são indexados a partir de 2). O vetor indica que o último vértice antes do vértice 2 é o vértice 3. Repetimos de novo o mesmo processo para ver o caminho mais curto entre 1 e 3. No vetor, na posição 3, temos o valor 1, que é a origem. Então, o caminho mais curto é 1,3,2.

Prova que o algoritmo funciona corretamente

Para efetuar a prova, vamos primeiro definir o conceito de caminho especial mais curto. Seja v₁ a origem. Para qualquer vértice v_i que não faz parte do conjunto S, o caminho especial mais curto é o caminho mais curto para alcançar v_i a partir de v₁ e que passa somente por vértices do conjunto S.

Para provar que o algoritmo funciona corretamente, é so provar o seguinte:

1. Se um vértice i pertence ao conjunto S, então D[i] contém o comprimento do caminho mais curto entre a origem e i.
2. Se um vértice i não faz parte do conjunto S, então D[i] contém o comprimento do caminho especial mais curto entre a origem e i.

A prova é por indução. Inicialmente os valores no vetor D contêm o valor da aresta que liga cada vértice ao vértice 1 (valor infinito se não tem aresta). Nenhum dos vértices, com a exceção do vértice 1, faz parte de S. Portanto, é trivial conferir que as duas propriedade são verdadeiras nesse caso. Isso é a base da indução. A hipótese de indução supõe que as duas condições são verdadeiras imediatamente antes de acrescentar um novo vértice v no conjunto S. Vamos ver agora o que acontece quando acrescentamos v no conjunto S.

1. Para cada vértice que já estava no conjunto S antes de acrescentar v, a primeira propriedade continua verdadeira. Por hipótese de indução, ja sabemos que D[v] é a distância do caminho especial mais curto até v. Se conseguirmos provar que o caminho mais curto até v passa somente por vértices do conjunto S, teremos a prova que D[v] é o valor do caminho mais curto e que acrescentando v no conjunto S respeitamos a primeira propriedade. Vamos supor então que existe um outro caminho mais curto até v. Consideramos agora x, o primeiro vértice desse caminho alternativo que não pertence a S. Isso é ilustrado na figura 2, onde em vermelho é indicado o caminho mais curto, e em preto o caminho especial mais curto.

   

   Figura 2

   Nesse caso, supondo que o grafo não contém nenhum peso negativo, a distância até v passando por x é maior ou igual à distância até x. Como esse caminho começa com um caminho especial até x e que por indução o comprimento D[x] dessa parte do caminho é mínima, sabemos que a distáncia total até v passando por x é maior ou igual a D[x]. Como v foi selecionado antes de x, devemos ter também D[x] D[v]. Isso implica que o caminho em vermelho, que é supostamente mais curto, deve possuir um comprimento maior ou igual ao comprimento do caminho especial indicado em preto, o que contradiz a hipótese. Portanto o caminho especial até v é o mais curto.
   
   

2. Consideramos agora o que acontece com os outros vértices diferentes de v que ficam fora do conjunto S. Seja w tal vértice. Quando v é acrescentado no conjunto S tem duas possibilidades no que concerne o caminho especial mais curto até w: ou ele fica igual, ou ele passa agora por v. Vamos então considerar o segundo caso.

   Parece que ainda tem duas possibilidades: ou o vértice v e o último no caminho até w ou ele não é. Vamos mostrar que o primeiro caso nunca vai acontecer. Suponhamos que o ultimo vértice antes de chegar a w é um vértice x diferente de v, como ilustrado na figura 3:

   

   Figura 3

   Esse caminho não pode ser mais curto, pois já existe um caminho mais curto (ou igual) até x que não inclui v (isso porque x já estava em S antes da adição de v e por indução já tinhamos um caminho mais curto). Então, o caminho especial mais curto é o menor entre o que passa por v antes de chegar a w e o que tinhamos antes de acrescentar v. E isso é exatamento o que o algoritmo verifica.

Análise do algoritmo

A inicialização do algoritmo exige um tempo em O(n). O loop é executado n-2 vezes e a cada iteração todos os vértices não atualmente no conjunto S são visitados. Na primeira iteração, visitaremos n-1 vértices, na segunda, n-2 vértices, e assim por diante. Podemos então deduzir que o tempo de execução é em O(n²).

Consideramos agora um grafo esparso. Mais especificamente, um grafo de a arestas e n vértices, onde a << n. Podemos melhorar o desempenho do algoritmo, utilizando uma estrutura de adjacência. Supondo que para cada vértice temos um campo que indica se ele pertence ao conjunto C, e que cada elemento da lista de adjacência associada a um vértice v indica não somente o vértice w ligado, mas também o peso d(v,w) de v para w, eis a versão modificada do algoritmo:

função Dijkstra(G: grafo): vetor[2..n] C := {2,3,...,n}   {Implicitamente S = N - C}
Para i := 2 até n:
D[i] :=   
Para cada vértice v adjacente ao vétice 1:
D[v] := d(1,v)
Repetir n-2 vezes:
v :=   Elemento de C que minimiza D[v]
C :=   C - {v}
Para cada vértice w adjacente a v:
Se w pertence a C:
D[w] :=   min(D[w],D[v]+ d[v,w])
Retornar D

Nesse caso, o loop mais interno não vai visitar todos os vértices do grafo, somente os que são adjacentes ao último vértice acrescentado. No total, o teste interno será executado a vezes, o que é proporcional a n no caso de um grafo esparso. Mas mesmo se isso melhora na prática, o algoritmo ainda é em O(n²) porque devemos ainda visitar todos os elementos do conjunto C para retirar o vértice que possui o menor valor.

É possível melhorar mais ainda, usando, além da estrutura de adjacência, um heap que contém um nodo para cada vértice v do conjunto C, ordenados em ordem crescente pelo valor D[v]. O tempo para inicializar o heap e em O(n). Consideramos agora o loop principal. Para retirar o vértice v do conjunto C que minimiza D[v], simplesmente retiramos o vértice que está na raiz do heap e ajustamos o heap. Sabemos que isso exige um tempo em O(log n). No que concerne o loop mais interno, devemos considerar todo vértice x adjacente a v que é no conjunto C. Nesse caso, talvez deveremos ajustar o valor D[x]. O ajustamento necessário no heap exige um tempo em O(log n). Em resumo, é preciso retirar n-2 vezes um vértice do conjunto C (exigindo uma atualização do heap a cada vez) e revisar o valor D[v] no máximo a vezes (isso também exige uma atualização do heap). Portanto, com essa implementação, o tempo de execução será em O((a+n)log n). Se o grafo é conexo, temos a n-1, e então um tempo de execução em O(a log n).

Programação dinâmica

O algoritmo de Dijkstra permite identificar todos os caminhos mais curtos a partir de um único vértice de origem. Utilizando a programação dinâmica, podemos obter o caminhmo mais curto entre qualquer par de vértices. Lembramos que a programação dinâmica consiste essencialmente em produzir soluções intermediárias que serão utilizadas incrementalmente para obter a solução final. Vamos primeiro ver uma solução interessante em teoria mas ineficiente na prática.

A idéia do nosso primeiro algoritmo é o seguinte. Seja um grafo direcionado representado por uma matriz de adjacência L[1..n,1..n]. Calculamos a cada etapa do algoritmo uma matriz D onde cada elemento D[i,j] representa o valor do caminho mais curto de k arestas entre i e j. Na etapa seguinte os valores das matrizes D e L são utilizadas para calcular a nova matriz D que contém os valores para k+1 arestas. Para obter o novo valor D[i,j], consideramos o valor D[i,u] + L[u,j] para todo vértice u e escolhemos o menor valor. Isto é, consideramos todos o caminhos de k vértices a partir de i, acrescentamos, para cada um desses caminhos, a arestas que falta para alcançar j e selecionamos o mais curto.

Eis o algoritmo:

função CamMaisCurtos(L[1..n, 1..n]: grafo): matriz [1..n,1..n] D := L
Repetir n-2 vezes:
Para i := 1 até n:
Para j := 1 até n:
min :=
Para k := 1 até n:
Se D[i,k]+L[k,j] < min então min := D[i,k]+L[k,j]
D'[i,j]:= min
D := D'
Retornar D

Considere agora o grafo ilustro na figura 4:

Figura 4

Eis as etapas da execução do algoritmo com o grafo da figura 4:

Iteração		D
Inicialização		0 5 50 0 15 5 30 0 15 15 5 0
1		0 5 20 10 20 0 10 5 30 35 0 15 15 20 5 0
2		0 5 15 10 20 0 10 5 30 35 0 15 15 20 5 0

Considerando agora o tempo de execução desse algoritmo, vemos que ele está em O(n⁴). Será que dá para fazer melhor? Sim, é possível. Vamos ver agora o algoritmo de Floyd, que também retorna o caminho mais curto entre qualquer par de vértices.

Seja G=(V,E) um grafo direcionado. Como antes, supomos que os vértices de G são enumerados de 1 até n. O grafo é representado por uma matriz de adjacência L onde L[i,i] = 0, L[i,j] 0 para i j, e L[i,j] = quando não existe nenhuma aresta entre i e j.

O princípio do algoritmo que vamos apresentar agora é o seguinte: O algoritmo efetua n iterações. Na iteração k do algoritmo obteremos uma matriz D cujos elementos na posição D[i,j] representam o caminho mais curto de i até j, entre todos que passam somente por vértices do conjunto C = {1,2,...,k}, isto é, um caminho que pode conter somente os vértices i e j e qualquer outro do conjunto C = {1,2,...,k}. Quando acrescentamos o vértice k+1, temos que atualizar todas as distâncias para ver se agora não temos um caminho mais curto passando pelo vértice k. O valor na posição D[i,j] muda somente se o valor D[i,k] + D[k,j] é menor. Nesse caso colocamos em D[i,j] o valor D[i,k] + D[k,j]. Quando o algoritmo pára, isto é, quando k = n, temos na matriz os valores dos caminhos mais curtos entre qualquer par de vértices.

Eis a descrição do algoritmo:

Para se convencer que o algoritmo funciona corretamento, de novo faremos um prova por indução. No início D[i,j] contém o valor da aresta entre i e j se tal aresta existe, senão. Como inicialmento o conjunto C é vazio, não pode ter vértice intermediário entre i e j, temos em D[i,j] o valor do caminho mais curto. Suponhamos agora que a hipótese é verdadeira para a iteração k. Se caminho entre i e j que passa por k+1 é mais curto, necessariamente os pedaços de i até k e de k até j são também os mais curtos. Já temos na matriz, nas posições D[i,k] e D[k,j], o valor desses caminhos mais curtos. Como o programa compara a soma desses dois valores com o valor encontrado em D[i,j] e escolhe o menor, também na etapa k+1 teremos os caminhos mais curtos que passam pelos vértices {1,2,...,k+1}.

É muito fácil ver que o algoritmo tem um tempo de execução em O(n³). Note que o mesmo problema pode ser resolvido aplicando n vezes o algoritmo de Dijkstra, começando cada vez com um vértice diferente. Nesse caso, teriamos também um tempo de execução em O(n³). Mas isso não significa que ambos têm a mesma eficiência. O algoritmo de Floyd tem que inicializar uma matriz de tamanho n x n. O algoritmo de Dijktra tem, dentro do primeiro loop, dois loops onde cada uma exige um tempo de execução na ordem de n. Também ele deve efetuar uma inicialização que exige um tempo em O(n) (isso repetido n vezes vai dar um total em O(n²)). Lembramos que usando uma estrutura de heap, podemos obter uma implementação do algoritmo de Dijkstra que está em O((a+n) log n), onde a é o número de arestas. Aplicando n vezes o algoritmo, obtemos um tempo de execução de n x O((a+n) log n) = O((an + n²) log n). Se o grafo é esparso, pode ser melhor utilizar o algoritmo de Dijkstra. Se o número de arestas se aproxima do grafo completo, provavelmente o algoritmo de Floyd será melhor.

A descrição do algorimo dada acima não permite identificar o caminho mais curto. Para obter isso, podemos modificar o algoritmo de maneira semelhante ao que foi feito com o algoritmo de Dijkstra. Utizaremos uma matriz P onde cada elemento P[i,j] aponta no último vértice (diferente de i) encontrado no caminho antes de chegar a j. A matriz P será atualizada cada vez que uma posição D[i,j] será atualizada, colocando o último vértice k considerado. No início, toda posição da matriz P recebe o valor 0. No final, para identificar o caminho mais curto entre i e j, é so percorrer os ponteiros a partir de P[i,j] até chegar a uma entrada que tem valor 0. Eis a versão modificada do algoritmo:

Eis as etapas da execução do algoritmo de Floyd com o grafo da figura 4:

Iteração		D		P
Inicialização		0 5 50 0 15 5 30 0 15 15 5 0		0  0 0 0 0  0 0 0 0  0 0 0 0  0 0 0
1		0 5 50 0 15 5 30 35 0 15 15 20 5 0		0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0
2		0 5 20 10 50 0 15 5 30 35 0 15 15 20 5 0		0 0 2 2 0 0 0 0 0 1 0 0 0 1 0 0
3		0 5 20 10 45 0 15 5 30 35 0 15 15 20 5 0		0 0 2 2 3 0 0 0 0 1 0 0 0 1 0 0
4		0 5 15 10 20 0 10 5 30 35 0 15 15 20 5 0		0 0 4 2 4 0 4 0 0 1 0 0 0 1 0 0

Exercícios

Exercício 5-1: Execute o algoritmo de Dijkstra com o grafo da figura 1, mas começando com o vértice 4. A resposta é a mesma?

Exercício 5-2: Para cada grafo ilustrado na figura 5, mostre cada passo da execução do algoritmo de Dijkstra.

Figura 5

Exercício 5-3: Dê um exemplo mostrando que se arestas de peso negativo são permitidas, o algoritmo de Dijkstra não funciona sempre corretamente.

Exercício 5-4: Se o algoritmo de Dijkstra é executado com um grafo desconexo, funciona mas é inutilmente ineficiente. Proponha uma modificação para torná-lo mais eficiente nesse caso.

Exercício 5-5: Inspire-se do algoritmo de Dijkstra para escrever um algoritmo que retorna o caminho mais comprido.

Exercício 5-6: Para cada grafo ilustrado na figura 5, mostre cada passo da execução do algoritmo de Floyd.

Exercício 5-7: Como o algoritmo de Floyd se comporta com um grafo que contém arestas de peso negativo? (Considere os casos onde existem circuitos de valor negativo e os casos onde não existe tal circuito)

Exercício 5-8: Considere uma aplicação onde não estamos interessados em conhecer os caminhos mais curtos, mas simplesmente a existência de um caminho entre dois vértices. Supondo uma representação de um grafo usando uma matriz L[1..n,1..n], onde L[i,j] = True se existe uma aresta entre i e j e False senão, proponha uma versão modificada do algoritmo de Floyd que retorna uma matriz D[i,j] onde D[i,j] = True se existe um caminho entre i e j e retorna False senão.

Exercício 5-9: Inspire-se do exercício 5-8 para escrever um algoritmo que testa se uma grafo é conexo.

Exercício 5-10: Modifique o algoritmo de Floyd para determinar o número de caminhos entre cada par de vértices.

Exercício 5-11: Modifique o algoritmo de Floyd para determinar o número de caminhos mais curtos entre cada par de vértices.