Distâncias com pesos e o algoritmo de Dijkstra

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

Edsger W. Dijkstra

Na página Distâncias e busca em largura, a distância de um vértice a outro de um grafo é medida em número de arcos. Nesta página, cada arco tem um peso numérico e a distância deve levar esse peso em conta. Trataremos de calcular a distância de um dado vértice a outro nesse grafo com pesos. Se os pesos forem não-negativos, o célebre algoritmo de Dijkstra (pronuncie algo entre Dêcstra e Dêicstra) resolve o problema.

Esta página foi inspirada em parte do capítulo 24 de CLRS.

Caminhos de peso mínimo

Suponha que cada arco vw de um grafo tem um peso (= weight) numérico f(vw). O peso de um caminho é a soma dos pesos dos arcos do caminho. O peso de um caminho P será denotado por f(P).

Um caminho P é f-mínimo se nenhum outro caminho com a mesma origem e o mesmo término de P tem peso menor que f(P). Em outras palavras, um caminho P de um vértice r a um vértice s é f-mínimo se f(P) ≤ f(Q) para todo caminho Q de rs.

A f-distância de um vértice r a um vértice s é o peso de um caminho f-mínimo que começa em r e termina em s. Se não existe caminho algum de rs, a f-distância é infinita. Quando f estiver subentendido, podemos dizer, simplesmente, distância. É claro que a distância de rs é, em geral, diferente da distância de sr.  Por isso, dizemos distância de r a s e não distância entre r e s.

Problema das distâncias com pesos:  Dado um vértice r de um grafo e uma atribuição f de pesos aos arcos do grafo, encontrar a f-distância de r a cada um dos demais vértices.

O problema faz sentido com quaisquer pesos, positivos ou negativos, mas fica traiçoeiro e muito mais difícil na presença de pesos negativos. Vamos nos restringir, então, às instâncias em que

f(vw) ≥ 0

para cada arco vw. Sob essa hipótese, podemos supor, sem perder generalidade, que todo caminho f-mínimo é simples. A expressão sem perder generalidade é uma referência à possibilidade de ciclos de peso nulo pendurados no caminho. Se removermos esses ciclos, o caminho fica simples e continua sendo f-mínimo.

Se f(vw) = 1 para todo arco vw, nosso problema se reduz ao problema das distâncias discutido na página Distâncias e busca em largura.

A solução de qualquer instância do problema será representada por um vetor dist indexado pelos vértices: para cada vértice v, dist[v] será a f-distância de r a v. Como f ≥ 0, teremos dist[r] = 0.

Exemplo A.  Considere o grafo com pesos f nos arcos definidos pela tabela a seguir.  Queremos encontrar as f-distâncias a partir do vértice 1.
vw)  1 2 1 3 2 4 2 5 3 4 3 5 4 2 4 6 5 6
f(vw10 20 70 80 50 60 0 10 10

Eis o vetor das distâncias a partir do vértice 1:

v]  1 2 3 4 5 6
dist[v0 10 20 70 80 80

Exercícios 1

  1. Encontre a f-distância de r a s no grafo descrito a seguir. Os vértices do grafo são r, w, z, s e os arcos, com os respectivos pesos, são dados pela tabela.
    uv)  rs rw wz zs
    f(uv4 1 1 1
  2. Encontre a f-distância de r a s no grafo descrito a seguir. Os vértices do grafo são r, z, s e os arcos, com os respectivos pesos, são dados pela tabela.
    uv)  rz zr zs
    f(uv−2 +1 +1
  3. Seja P um caminho de um vértice r a um vértice s. Mostre que P tem uma subsequência P′ que é um caminho simples de rs. Mostre que se f ≥ 0 então f(P′) ≤ f(P). Conclua que se P é f-mínimo então P′ também é f-mínimo.

Preliminares

Nossa primeira descrição do algoritmo de Dijkstra para o problema das distâncias com pesos será feita num nível de abstração bastante alto. O algoritmo é iterativo e cada iteração começa com um vetor dist indexado pelos vértices. No começo da primeira iteração, dist[r] = 0 e dist[w] = ∞ para todo vértice w ≠ r. Digamos que a franja é o conjunto de todos os arcos vw tais que dist[v] < ∞ e dist[w] = ∞. O processo iterativo pode então ser descrito assim:

enquanto a franja não estiver vazia,
.oo tome vw na franja tal que dist[v] + f(vw) é mínimo
.oo e faça dist[w] := dist[v] + f(vw).

No fim de cada iteração, dist[w] deixa de ser ∞ e portanto a franja se altera. Quando a franja fica vazia, o processo iterativo termina e dist é o vetor das f-distâncias a partir de r.

figs/mine/diwheel6-j02-invert21.png
Exemplo B.  Queremos encontrar as f-distâncias a partir do vértice 0 no grafo com custos nos arcos definido a seguir.
vw)  0 2 0 3 0 4 2 4 3 4 3 5 4 1 4 5 5 1 1 2
f(vw70 50 30 10 10 20 0 30 50 30

Veja o rastreamento da execução do algoritmo de Dijkstra, tal como descrito acima. No início de cada iteração, registramos o vetor dist e os arcos da franja (com - no lugar de ):

dist) franja
0 - - - - -       0 2 0 3 0 4
0 - - - 30 - 0 2 0 3 4 1 4 5
0 30 - - 30 - 0 2 0 3 4 5 1 2
0 30 - 50 30 - 0 2 4 5 1 2 3 5
0 30 - 50 30 60       0 2 1 2
0 30 60 50 30 60

O arco da franja que será escolhido na próxima iteração está pintado de vermelho.

Exercícios 2

  1. Prove que o algoritmo de Dijkstra, tal como descrito acima, consome Ο(nm) unidades de tempo, sendo n o número de vértices e m o número de arcos do grafo. Mostre que no pior caso o algoritmo consome Ω(nm) unidades de tempo.
  2. Prove que o algoritmo de Dijkstra, tal como descrito acima, está correto.

O algoritmo de Dijkstra

Tal como descrito na seção anterior, o algoritmo de Dijkstra é muito lento. Para dar uma descrição mais eficiente, é preciso reorganizar o processo iterativo. No início de cada iteração, teremos um certo conjunto Q de vértices. Para todo vértice v fora de Q, teremos dist[v] < ∞. No início da primeira iteração, Q será o conjunto de todos os vértices do grafo, dist[r] valerá 0, e dist[w] valerá ∞ para todo w ≠ r. O processo iterativo consiste no seguinte:

enquanto Q não estiver vazio,
.oo escolha q em Q que minimize dist[q],
.oo remova q de Q,
.oo para cada arco qw,
.ooooo se dist[w] > dist[q] + f(qw)
.oooooooo então dist[w] := dist[q] + f(qw).

A operação nas duas últimas linhas é conhecida como relaxação do arco qw. A ideia da relaxação é óbvia: se algum caminho de r até q tem peso dist[q] então existe um caminho de peso dist[q] + f(qw) de r até w.

Para reescrever o algoritmo de maneira mais formal, suponha que o grafo é representado por um vetor Adj de listas de adjacência. O conjunto Q será representado por uma fila-com-prioridades (mas não vamos adotar, por enquanto, uma implementação específica da fila).

1Dijkstra (G, f, r)     f ≥ 0
11 . para cada v em V(G)
12 .ooo dist[v] := ∞
13 . dist[r] := 0
14 . Q := Nova-Fila-com-Prioridades ( )
15 . para cada v em V(G)
16 .ooo Insira-na-Fila (v, Q)
17 . enquanto Q não está vazia faça
18 .ooo q := Extraia-Min (Q)
19 .ooo para cada w em Adj[q] faça
10 .oooooo se dist[w] > dist[q] + f(qw)
11 .ooooooooo Diminua-Chave (w, Q, dist[q] + f(qw))
12 . devolva dist

A operação Nova-Fila-com-Prioridades ( ) cria uma fila-com-prioridades vazia. A operação Insira-na-Fila (v, Q) insere o vértice v na fila Q de acordo com a prioridade dist[v]. A operação Extraia-Min (Q) remove de Q um vértice q para o qual dist[q] é mínimo. A operação Diminua-Chave (w, Q, c) faz dist[w] := c e o que mais for preciso para restabelecer a estrutura de Q.

Na linha 11, o vértice w está necessariamente em Q, como veremos adiante. Assim, cada iteração altera apenas as componentes de dist que correspondem a vértices de Q.

Exercícios 3

  1. Compare o código de Dijkstra com o do algoritmo Distâncias.
  2. Critique a seguinte afirmação: no início de cada repetição do bloco de linhas 8-11 de Dijkstra, para cada vértice v, dist[v] é a f-distância de rv.
  3. No fim da linha 8 de Dijkstra, podemos ter dist[q] = ∞? Discuta essa possibilidade.
  4. [CLRS]  Na linha 7 de Dijkstra, posso interromper o processo iterativo quando Q tiver apenas 1 vértice? Posso interromper o processo quando dist[w] = ∞ para todo w em Q?
  5. Escreva uma versão do algoritmo Dijkstra que não coloque todos os vértices em Q logo no início. Insira um vértice w em Q somente quando dist[w] ficar finito. (Sugestão: inicialmente, pinte todos os vértices de branco; quando um vértice for inserido em Q, pinte-o de cinza; quando sair de Q, pinte-o de preto.)
  6. ★ Mostre que o algoritmo Dijkstra pode produzir resultados errados se algum arco tiver peso negativo. (À primeira vista, não há nada no código que dependa explicitamente da condição f ≥ 0.) Procure dar um exemplo que não tenha ciclo de peso negativo.

Desempenho

O consumo de tempo do algoritmo Dijkstra depende da implementação da fila-com-prioridades Q. Discutiremos duas implementações. Como veremos, o algoritmo é assintoticamente mais rápido com a fila mais simples que com a fila mais sofisticada se nos restingirmos a grafos densos.

Implementação simples da fila.  Suponha que a fila Q é implementada como um vetor de vértices em ordem arbitrária. Nesse caso, Q funciona como um mero conjunto de vértices (certamente não como uma fila no sentido usual da palavra).

O bloco de linhas 1-4 consome Ο(n) unidades de tempo, sendo n o número de vértices. O bloco de linhas 5-6 também consome Ο(n) unidades de tempo, pois cada execução de Insira-na-Fila consome tempo constante (ou seja, independente do tamanho do grafo).

O bloco de linhas 8-11 é repetido n vezes, pois o tamanho da fila Q diminui a cada iteração.

No pior caso, cada execução de Extraia-Min na linha 8 consome tempo proporcional ao tamanho de Q, pois pode vir a examinar todos os vértices de Q. Assim, as n execuções da linha 8 consomem Ο(n²) unidades de tempo.

Cada execução de Diminua-Chave na linha 11 consome tempo constante, pois consiste na atribuição dist[w] := dist[q] + f(qw) e nada mais. Assim, cada execução do par de linhas 10-11 consome tempo constante. O número total de execuções desse par de linhas em todas as n repetições do bloco de linhas 8-11 é igual ao número, m, de arcos do grafo. Assim, a soma dos consumos de tempo de todas as execuções do bloco de linhas 10-11 é Ο(m).

Concluímos que o bloco de linhas 7-11 consome Ο(n² + m) unidades de tempo. O consumo total do algoritmo é, portanto,

Ο(n² + m)

unidades de tempo. Essa cota superior é justa, pois existem famílias de grafos para as quais o algoritmo consome Ω(n² + m) unidades de tempo.

Como m < n², podemos dizer que o algoritmo consome tempo Ο(n²). Mas é preciso entender isso em função do tamanho das instâncias do problema. Adote n + m como tamanho de uma instância. Se tratarmos apenas de instâncias esparsas, ou seja, instâncias cujo tamanho é da ordem de n, o algoritmo é quadrático. Se tratarmos apenas de instâncias densas, ou seja, instâncias cujo tamanho é da ordem de n², o algoritmo é linear.

Implementação sofisticada da fila.  Suponha agora que a fila-com-prioridades Q é implementada como um min-heap.

O bloco de linhas 4-6 consome Ο(n) unidades de tempo de acordo com a seção Construção de um max-heap na página A estrutura heap.

O bloco de linhas 8-11 é repetido n vezes, pois o tamanho da fila Q diminui a cada iteração.

Cada execução da rotina Extraia-Min na linha 8 consome Ο(lg n) unidades de tempo. Assim, as n execuções da linha 8 consomem Ο(n lg n) unidades de tempo.

Cada execução de Diminua-Chave na linha 11 consome Ο(lg n) unidades de tempo, e portanto cada execução do par de linhas 10-11 consome Ο(lg n) unidades de tempo. O número total de execuções desse par de linhas em todas as n repetições do bloco de linhas 10-11 é igual ao número, m, de arcos do grafo. Assim, a soma dos consumos de tempo de todas as execuções do bloco de linhas 10-11 é Ο(m lg n).

Concluímos que o bloco de linhas 7-11 consome Ο(n lg n + m lg n) unidades de tempo. O consumo total do algoritmo é, portanto,

Ο((n + m) lg n)

unidades de tempo. Essa cota superior é justa, pois existem famílias de grafos que levam o algoritmo a consumir Ω((n + m) lg n) unidades de tempo.

Se tratarmos apenas de grafos esparsos, ou seja, grafos em que m é da ordem de n, o tamanho do grafo é da ordem de n e o algoritmo consome tempo Ο(n lg n). Entretanto, se tratarmos apenas de grafos densos, ou seja, grafos em que m é da ordem de n², o tamanho do grafo é da ordem de n² e o algoritmo consome tempo Ο(n² lg n). Em ambos os casos, o algoritmo é linearítmico.

Exercícios 4

  1. Reescreva o código do algoritmo Dijkstra de modo a usar explicitamente uma implementação simples da fila Q. Escreva implementações inline de Nova-Fila-com-Prioridades, Insira-na-Fila, Extraia-Min e e Diminua-Chave (ou seja, as implementações devem ser embutidas no código do algoritmo).
  2. Reescreva o código do algoritmo Dijkstra de modo a usar explicitamente um heap para implementar a fila Q. Escreva implementações inline de Nova-Fila-com-Prioridades, Insira-na-Fila, Extraia-Min e e Diminua-Chave (ou seja, as implementações devem ser embutidas no código do algoritmo).
  3. Adapte o código do algoritmo Dijkstra para grafos representados por matriz de adjacência. Calcule o consumo de tempo dessa versão.

Prova da correção do algoritmo de Dijkstra

Não é óbvio que o algoritmo de Dijkstra resolve o problema das distâncias com pesos restrito a pesos não-negativos. Para se convencer de que o algoritmo está correto, é preciso entender o estado de coisas no início de cada iteração.

No início de cada iteração do bloco de linhas 8-11 do algoritmo, diremos que um vértice é cinza (ou imaturo) se está na fila Q e preto (ou maduro) em caso contrário. Valem então os seguintes invariantes:

  1. para todo vértice v tal que dist[v] < ∞, existe um caminho quase preto C de r a v tal que f(C) = dist[v];
  2. para todo vértice preto v e qualquer caminho B de rv tem-se f(B) ≥ dist[v];
  3. para todo vértice cinza v e qualquer caminho quase preto C de r a v tem-se f(C) ≥ dist[v].

Em i e iii, um caminho é considerado quase preto se todos seus vértices são pretos exceto talvez o último. (Por exemplo, um caminho cujo vértices são todos pretos é considerado quase preto. Outro exemplo: um caminho de comprimento 0 cujo único vértice é cinza é considerado quase preto.)

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

Suponha agora que estamos no início da última iteração. Como Q está vazio, todos os vértices são pretos. Portanto, para todo vértice v, em virtude do invariantes i e ii, o número dist[v] é a f-distância se rv. (Em particular, dist[v] = ∞ se e somente se v não está ao alcance de r.) Isso prova que o algoritmo Dijkstra esta correto (desde que provemos que os invariantes estão corretos.)

Exercícios 5

  1. Prove os invariantes do algoritmo Dijkstra. [Solução]
  2. Prove que na linha 11 do algoritmo Dijkstra, o vértice w está necessariamente em Q. (Sugestão: use o invariante ii.)
  3. Prove que no início de cada iteração no algoritmo Dijkstra, para cada vértice cinza w, dist[w] = min (dist[v] + f(vw)), sendo o mínimo tomado sobre todos os arcos vw para os quais v é preto.
  4. Prove que no início de cada iteração no algoritmo Dijkstra, dist[v] ≤ dist[w] para todo v fora de Q e todo w em Q.
  5. [CLRS, CLRS3]  Suponha que um dado grafo com pesos nos arcos não tem ciclos de peso negativo. Suponha que todos os arcos de peso negativo têm ponta inicial num certo vértice r Mostre que o algoritmo Dijkstra calcula corretamente as distâncias a partir de r nesse grafo.

Exercícios 6

  1. [CLRS, CLRS3]  Suponha que a cada arco vw de um grafo está associado um número racional conf(vw) no intervalo [0,1]. Este número representa a confiabilidade do arco vw, ou seja, a probabilidade de que o arco não vai quebrar. Dê uma definição apropriada para a confiabilidade de um caminho. Encontre caminhos de confiabilidade máxima de um vértice r a cada um dos demais vértices.
  2. [IP 436]  Suponha que os arcos de um grafo têm pesos não-negativos. Queremos encontrar um caminho de r a s que tenha peso máximo. É possível resolver o problema trocando Extraia-Min por Extraia-Max na linha 8 do algoritmo Dijkstra? (É claro que esse ajuste deve ser acompanhado de outros ajustes óbvios nas linhas 2 e 8.)

Caminhos de peso mínimo

Até aqui tratamos apenas das f-distâncias. Mas os caminhos f-mínimos que realizam essas distâncias são igualmente importante. É fácil aparelhar o algoritmo Dijkstra de modo a obter, para cada vértice s ao alcance de r, um caminho de rs cujo peso é igual à f-distância de rs. Basta calcular um vetor de pais, digamos pai, que represente esses caminhos.

Este é um bom momento para levantar a seguinte questão: Dado um caminho P de rs, como podemos convencer um amigo cético que P é f-mínimo? A seguinte ideia simples mas poderosa leva a uma resposta. Digamos que um potencial é qualquer atribuição de números aos vértices do grafo. Se

h[v] + f(vw) h[w]

para todo arco vw, diremos que o potencial h é relaxado. Temos então a seguinte

Condição de minimalidade:  Dado um caminho P com origem r e término s num grafo com pesos f nos arcos, se existe um potencial relaxado h tal que h[r] + f(P) = h[s] então P é f-mínimo.

Esboço da prova: Seja Q um caminho qualquer de rs. Basta provar que f(Q) ≥ f(P). Suponha, para simplificar, que Q é (rv, ws). Como h é relaxado, temos

f(Q) = f(rv) + f(vw) + f(ws)
h[v] − h[r] + h[w] − h[v] + h[s] − h[w]
= h[s] − h[w] + h[w] − h[v] + h[v] − h[r]
= h[s] − h[r]
= f(P) ,

CQD.

Para aplicar essa condição de minimalidade, precisamos de um potencial relaxado apropriado. Onde encontrar um tal potencial? Resposta: as f-distâncias a partir de r são um potencial relaxado!

Exercícios 7

  1. ★ Reescreva o algoritmo Dijkstra acrescentando um vetor de pais.
  2. ★ Seja r um vértice de um grafo e f uma atribuição de pesos aos arcos do grafo. Seja dist um vetor tal que dist[v] é a f-distância de rv. Prove que dist é um potencial relaxado.
  3. [CLRS3]  Escreva um algoritmo que receba um vértice r de grafo, uma atribuição f de pesos não-negativos aos arcos do grafo, e um vetor h que atribui números aos vértices e verifique se h é um potencial relaxado.

Apêndice: abstrações

O problema das distâncias com pesos e o algoritmo de Dijkstra são casos particulares de várias abstrações importantes:

  1. Subestrutura ótima (= optimal substructure property): todo segmento de um caminho f-mínimo é f-mínimo.
  2. Algoritmo guloso: em cada iteração, o algoritmo de Dijkstra escolhe o vértice mais barato sem preocupar-se com as consequências dessa escolha a longo prazo.
  3. Relaxação de arcos: o algoritmo de Dijkstra nada mais faz que sistematicamente relaxar arcos.
  4. Potencial relaxado: as f-distâncias a partir de um vértice são um potencial relaxado.