Distâncias com pesos e o algoritmo de Dijkstra

Computer science is no more about computers than astronomy is about telescopes.

Edsger W. Dijkstra

 

Esta página foi inspirada em parte do capítulo 24 de CLRS. Ela trata trata do algoritmo de Dijkstra [pronuncie algo entre Dêcstra e Dêicstra],  que generaliza o algoritmo Distâncias.

Veja também os verbetes Shortest path problem e Dijkstra's algorithm na Wikipedia.

Passeios e caminhos de peso mínimo

Suponha que cada arco uv de um digrafo tem um  peso numérico  f(uv). Se P é um passeio, vamos denotar por  f(P)  o peso do passeio, ou seja, a soma dos pesos dos arcos do passeio.  Um passeio P de um vértice r a um vértice s tem peso mínimo se

f(P) ≤ f(P′)

para todo passeio P′ de rs.  Diremos também que P é um passeio f-mínimo.  A f-distância de um vértice r a um vértice s é o peso de um passeio f-mínimo de rs.

Problema das distâncias com pesos:  Dado um vértice r de um digrafo e uma função f que atribui um peso numérico a cada arco do digrafo, encontrar a f-distância de r a cada um dos demais vértices.

O problema faz sentido com quaisquer pesos reais (positivos ou negativos), mas fica muito mais difícil na presença de pesos negativos. Vamos supor, portanto, que

f(uv) ≥ 0   para cada arco uv.

Sob essa hipótese, todo passeio f-mínimo é necessariamente um caminho.  (Quase! A rigor, não é bem assim, por causa dos eventuais arcos de peso nulo. Mas posso garantir que para todo passeio f-mínimo P de r a s existe um caminho C de r a s tal que f(C) = f(P).)

Se f(uv) = 1 para todo arco uv então o problema desta página é idêntico ao problema das distâncias discutido na página Distâncias. Portanto, o problema a ser discutido aqui é uma generalização daquele outro.

Exercícios

  1. Encontre a f-distância de r a s no digrafo descrito a seguir. O digrafo tem vértices r, w, zs. Seus arcos e os respectivos pesos são dados pela tabela abaixo.
    uv  rs rw wz zs
    f(uv4 1 1 1
  2. Encontre a f-distância de r a s no digrafo descrito a seguir. O digrafo tem vértices r, z e s. Seus arcos e os respectivos pesos são dados pela tabela abaixo.
    uv  rz zr zs
    f(uv−2 +1 +1

Algoritmo de Dijkstra

O algoritmo descrito abaixo resolve nosso problema quando não há arcos de peso negativo. O algoritmo recebe um digrafo com vértices 1, 2, …, n e arcos definidos por listas de adjacência Adj[1..n]. Recebe também um vértice r e uma função f que atribui um peso positivo ou nulo a cada arco.  O algoritmo devolve a f-distância de r a cada um dos vértices do digrafo.

  Dijkstra (n, Adj, f, r)       comentário: f ≥ 0
1o para  u ← 1  até  n  faça
1oooo dist[u] ← ∞
1o dist[r] ← 0
1o QCria-Fila-Vazia ( )
1o para v crescendo de 1 até n faça
1oooo Insere-na-Fila (v, Q)
1o enquanto  Q  não está vazia faça
1oooo uExtrai-Min (Q)
1oooo para cada  v  em  Adj[u]  faça
10  ooooooo se  dist[u]+f(uv) < dist[v]
11  oooooooooo então  Diminui-Chave (v, Q, dist[u]+f(uv))
12  o devolva  dist[1..n]

(Compare com o algoritmo Distâncias.)  O subalgoritmo Cria-Fila-Vazia cria uma fila de prioridades vazia;  as prioridades são ditadas por dist.  O comando Insere-na-Fila(v,Q) insere o vértice v na fila Q.  O comando Extrai-Min retira da fila um vértice u para o qual dist[u] é mínimo.  O comando Diminui-Chave(v,Q,novo) na linha 11 faz dist[v] ← novo e o que mais for preciso para restaurar a estrutura da fila de prioridades Q.

A operação no par de linhas 10-11 é conhecida como relaxação do arco uv. A ideia é óbvia: se existe um passeio de peso dist[u] de r até u então também existe um passeio de peso dist[u]+f(uv) de r até v.

Para entender por que o algoritmo funciona corretamente, é preciso entender o estado de coisas no início de cada iteração. Para simplificar a discussão, diremos que um vértice u é

No início de cada iteração do bloco de linhas 8-11 valem os seguintes invariantes:

  1. para todo vértice x tal que dist[x] < ∞, existe um passeio P de r a x tal que f(P) = dist[x];
  2. f(Q) ≥ dist[x] para todo passeio Q que começa em r e termina em um vértice preto x;
  3. f(R) ≥ dist[u] para todo passeio que começa em r, termina em um vértice cinza u e não tem outros vértices cinza além de u.

A propriedade i afirma que  dist[x] é uma estimativa por cima da f-distância de rx.  A união das propriedades i e ii garante que  se x é preto então dist[x] é a f-distância correta de rx.  A propriedade iii garante que qualquer vértice cinza que minimiza dist está pronto para se tornar preto sem violar ii.

Exercícios

  1. [CLR 25.2-3]   Que acontece se a execução do algoritmo Dijkstra for interrompida quando a fila tiver apenas um elemento?
  2. Mostre que as propriedades invariantes i, ii e iii enunciados acima são de fato válidas.
  3. Mostre que o algoritmo abaixo é equivalente ao algoritmo Dijkstra. (Na prática, essa versão pode ser um pouco mais eficiente que Dijkstra, graças à verificação da cor de v na linha 11, embora o eventual ganho de eficiência não afete o consumo de tempo no pior caso.)  Compare com o algoritmo Busca-em-Largura.
      Dijkstra-Cinza-e-Preto (n, Adj, f, r)
    1o para  u ← 1  até  n  faça
    1oooo cor[u] ← cinza
    1oooo dist[u] ← ∞
    1o dist[r] ← 0
    1o QCria-Fila-Vazia ( )
    1o para v crescendo de 1 até n faça
    1oooo Insere-na-Fila (v, Q)
    1o enquanto  Q  não está vazia faça
    1oooo uExtrai-Min (Q)
    10  oooo para cada  v  em  Adj[u]  faça
    11  ooooooo se  cor[v] = cinza  e  dist[u]+f(uv) < dist[v]
    12  oooooooooo então  Diminui-Chave (v, Q, dist[u]+f(uv))
    13  oooo cor[u] ← preto
    14  o devolva  dist[1..n]
  4. Critique a seguinte versão do algoritmo de Dijkstra.  Compare com o algoritmo Busca-em-Largura.
      Dijkstra-Branco-Cinza-Preto (n, Adj, f, r)
    11 o para u ← 1 até n faça
    12 oooo cor[u] ← branco
    13 oooo dist[u] ← ∞
    14 o cor[r] ← cinza
    15 o dist[r] ← 0
    16 o QCria-Fila-Vazia ( )
    17 o Insere-na-Fila (r, Q)
    18 o enquanto  Q  não está vazia faça
    19 oooo uExtrai-Min (Q)
    10 oooo para cada v em Adj[u] faça
    11 ooooooo se cor[v] = branco
    12 oooooooooo então cor[v] ← cinza
    13 oooooooooo então dist[v] ← dist[u]+f(uv)
    14 oooooooooo então Insere-na-Fila (v, Q)
    15 oooooooooo senão  se cor[v] = cinza e dist[u]+f(uv) < dist[v]
    16 oooooooooo senão ooo então Diminui-Chave (v, Q, dist[u]+f(uv))
    17 oooo cor[u] ← preto
    18 o devolva  dist[1..n]

Consumo de tempo do algoritmo

O consumo de tempo do algoritmo Dijkstra depende criticamente da implementação da fila de vértices. Discutiremos duas implementações.

Implementação simplória da fila

Suponha que a fila é simplesmente um conjunto de vértices (na prática, os elementos da fila podem ser armazenados em um vetor, em ordem arbitrária). Nesse caso, o bloco de linhas 4-6 consome tempo proporcional a n  e  cada execução de Extrai-Min consome tempo proporcional a  n  no pior caso, pois é preciso examinar todos os elementos da fila.  A rotina Diminui-Chave não faz nada.

O bloco de linhas 8-11 será repetido no máximo n vezes, pois um vértice sai da fila em cada iteração e não há inserção de novos vértices na fila.  Portanto, o consumo de tempo de todas as execuções da linha 8  é  Ο(n²).

O consumo de tempo de cada execução do bloco de linhas 9-11 é proporcional a n no pior caso, pois cada vértice pode ter até n−1 vizinhos.  Portanto, o consumo de tempo de todas as execuções do bloco de linhas 9-11  é  Ο(n²).  (Poderíamos reduzir essa estimativa para Ο(m), mas esse refinamento seria supérfluo para a implementação simplória que estamos estudando.)

Assim, o consumo total de tempo do algoritmo Dijkstra é

Ο(n²) .

O algoritmo não pode ser considerado quadrático pois o tamanho de uma instância do problema é n+m e não n.  Se tratarmos apenas de digrafos densos, em que m é da ordem de n², o algoritmo é linear.

Implementação sofisticada da fila

A fila de prioridades pode ser estruturada como um min-heap (basta adaptar as funções que manipulam um max-heap).  Nesse caso, o bloco de linhas 4-6 consome tempo proporcional a  n lg n  (veja construção de um heap). Cada execução da rotina Extrai-Min consome tempo constante (ou seja, independente de n).  A rotina Diminui-Chave consome de tempo proporcional a  lg n.

O bloco de linhas 8-11 será repetido no máximo n vezes, pois um vértice sai da fila em cada iteração e não há inserção de novos vértices na fila.  Portanto, o consumo de tempo de todas as execuções da linha 8 é

Ο(n).

O número total de execuções do bloco de linhas 9-11 é limitado pelo número m de arcos. Assim, o consumo de tempo de todas as execuções do bloco de linhas 9-11 é

Ο(m lg n).

O consumo total de tempo do algoritmo Dijkstra é Ο(n lg n + n + m lg n) , ou seja,

Ο((n+m) lg n).

Conclusão: A menos que m seja da ordem de n², a implementação sofisticada é mais rápida que a simplória para valores grandes de n.

Exercícios

  1. Escreva uma versão detalhada do algoritmo Dijkstra que use um min-heap para implementar a fila de prioridades.
  2. Escreva uma versão detalhada do algoritmo Dijkstra usando uma matriz de adjacência para representar o digrafo. Calcule o consumo de tempo dessa versão.

Mais exercícios

  1. [CLR 25.2-4, CLRS 24.3-4]   A cada arco uv de um digrafo está associado um número racional conf(uv) no intervalo [0,1]. Este número representa a confiabilidade do arco uv, ou seja, a probabilidade de que o arco não vai quebrar nem desaparecer. Dê uma definição apropriada para a confiabilidade de um passeio. Encontre passeios de confiabilidade máxima de um vértice r a cada um dos demais vértices.
  2. [CLR 25.2-2]   Mostre que o algoritmo Dijkstra pode produzir resultados errados se f(uv) < 0 para algum arco uv. Mostre que isso pode acontecer mesmo que o digrafo não tenha ciclos de peso negativo.
  3. [IP 436]  Suponha que os arcos de um digrafo têm pesos positivos. Queremos encontrar um passeio de r a s que tenha peso máximo. É possível resolver o problema trocando Extrai-Min por Extrai-Máx na linha 8 do algoritmo Dijkstra? (É claro que esse ajuste deve ser acompanhado de outros ajustes óbvios nas linhas 210.)

Apêndice: passeios de peso mínimo

Seria muito interessante obter não só a f-distância de um vértice r a um vértice s mas também um passeio que realiza essa distância (ou seja, um passeio P de rs que minimize f(P)).  Poderíamos tratar desse assunto imediatamente, mas eu prefiro fazer isso mais tarde, depois que tiver discutido arborescências.



Valid HTML 4.01 Strict Valid CSS!