Análise de Algoritmos | Aulas | Dicionário | Índice

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 r a s.

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 r a s, a f-distância é infinita. Quando f estiver subentendido, podemos dizer, simplesmente, distância. É claro que a distância de r a s é, em geral, diferente da distância de s a r.  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.

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:

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.

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:

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).

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.

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.

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 r a v 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 r a v. A união das propriedades i e ii afirma que se v é preto então dist[v] é a f-distância de r a v. 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 r a v. (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.)

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 r a s cujo peso é igual à f-distância de r a s. 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 r a s, 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 r a s. Basta provar que f(Q) ≥ f(P). Suponha, para simplificar, que Q é (r, v, w, s). Como h é relaxado, temos

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!

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.