Algoritmos para Grafos  |  Índice

Caminhos de custo mínimo

Este capítulo é uma introdução geral ao problema do caminho de custo mínimo em grafos com custos arbitrários (positivos e negativos) nos arcos.  (O capítulo Caminhos de comprimento mínimo fez uma introdução análoga no caso em que os arcos não têm custos.)  O problema tem sutilezas que precisam ser bem compreendidas antes que possamos tentar resolvê-lo.  Algoritmos para o problema serão discutidos nos próximos capítulos.

A presença de arcos de custo negativo torna o problema escorragadio e anti-intuitivo. O problema fica especialmente difícil (NP-difícil, no jargão técnico) se o grafo tiver ciclos de custo negativo.

Sumário:

TinyNetwork-x.png TinyNetwork-x-weights.png       tinyEWDn-x.png tinyEWDn-weights.png

Caminhos mínimos e distâncias

Num grafo com custos nos arcos, o custo de um caminho é a soma dos custos dos arcos do caminho.  (Convém lembrar que, por definição, caminhos não têm arcos repetidos, e portanto cada arco do caminho contribui uma só vez para o custo.)  Se todos os arcos têm custo 1, por exemplo, o custo do caminho é igual ao seu comprimento.

Um caminho B é mais barato que um caminho C se tiver custo menor que o de C.  Dizemos que um caminho C  tem custo mínimo  se [!] nenhum caminho com a mesma origem e o mesmo término de C é mais barato que C.

Problema do caminho de custo mínimo:  Dados vértices st de um grafo com custos nos arcos, encontrar um caminho de custo mínimo com origem s e término t.

Se não houver caminho algum de st, o problema não tem solução.  Caso contrário, o problema certamente tem solução, pois o conjunto de diferentes caminhos com origem s e término t é finito, uma vez que caminhos não têm arcos repetidos.

É comum abreviar a expressão caminho de custo mínimo e dizer, simplesmente, caminho mínimo (Portanto, o significado da expressão caminho mínimo depende do contexto. Se os arcos do grafo têm custos, a expressão subentende o custo do caminho; senão, subentende o comprimento do caminho, conforme o capítulo Caminhos de comprimento mínimo.)

Se todos os custos são positivos, a relação entre o comprimento e o custo de um caminho é intuitiva: qualquer pedaço do caminho é mais barato que o caminho todo. Se há arcos de custo negativo, a relação entre o comprimento e o custo é traiçoeira, pois um pedaço do caminho pode ser mais caro que o caminho todo.

Arcos de custo negativo ocorrem naturalmente em muitos problemas práticos. Se custo positivo representa gasto, custo negativo representa ganho. Assim, quando há arcos de custo negativo, um caminho mínimo maximiza o lucro.

Distâncias.  A  distância  de um vértice s a um vértice t é o custo de um caminho mínimo com origem s e término t.  A distância de s a t é  d  se e somente se algum caminho de st tem custo d e nenhum caminho de s a t tem custo menor que d.

É claro que a distância de st é, em geral, diferente da distância de ts.  Por isso, dizemos distância de s a t e não distância entre s e t.

Se todos os arcos do grafo têm custo positivo e t está ao alcance de s, a distância de st é positiva.  Se há arcos de custo negativo, a distância de st pode ser negativa.  Se t não está ao alcance de s, a distância de st não está definida (ou, se preferir, é infinita).

TinyNetwork-x.png

Exemplo A.  A tabela a seguir mostra um grafo com custos positivos nos arcos.  (O comprimento geométrico de cada arco na figura é proporcional ao seu custo.)

4-5 5-4 4-7 5-7 7-5 5-1 0-4 0-2 7-3 1-3 2-7 6-2 3-6 6-0 6-4
 35  35  37  28  28  32  38  26  39  29  34  40  52  58  93

Considere os caminhos que vão de 06.  O caminho  0-2-7-5-1-3-6  não tem custo mínimo pois o caminho  0-2-7-3-6  é mais barato.  O custo desse último caminho é 26+34+39+52 = 151.  Esse caminho é mínimo? A distância de 0 a 6 é 151?

    0   
   / \  
  1 — 2 

Exemplo B.  A tabela abaixo define um grafo com custos nos arcos. Considere os caminhos que começam no vértice 0.

0-1  0-2  2-0  1-2
 10    3    5  -20

O caminho  0-2  não é mínimo pois  0-1-2  é mais barato.  O caminho fechado  0-1-2-0  tem custo -5. Esse caminho é mínimo. Portanto, a distância de 00 é  -5.

Exercícios 1

  1. Seja v-w um arco de custo mínimo num grafo com custos nos arcos. Qual a distância de vw?
  2. Encontre um caminho mínimo de 07 no grafo com custos nos arcos definido a seguir.
    0-7 0-1 1-2 2-3 3-4 4-5 5-6 6-7
     90  10  10  10  10  10  10  10
    
  3. Encontre um caminho mínimo de 04 no grafo com custos nos arcos definido a seguir.
    0-1 1-2 2-3 3-1 1-4
      5   1   1  -4   5
    
  4. Mostre que um grafo pode ter mais de um caminho mínimo de um dado vértice s a um dado vértice t. (Por isso dizemos um caminho mínimo e não o caminho mínimo.)
  5. Seja G uma árvore radicada com custos no arcos. Mostre que todo caminho em G tem custo mínimo.
  6. Seja s um sorvedouro de um grafo com custos nos arcos. Qual o custo de um caminho mínimo dentre todos os que têm origem s?
  7. ★ Suponha que um grafo tem um ou mais arcos de custo negativo. Mostre que um caminho mínimo pode não ser simples. Mostre também que um segmento de um caminho mínimo pode não ser um caminho mínimo.
  8. Redução de custo a comprimento.  Mostre como o algoritmo para caminhos de comprimento mínimo pode ser usado para calcular um caminho mínimo num grafo com custos (inteiros) estritamente positivos nos arcos.  (Sugestão: Acrescente novos vértices subdividindo cada arco de custo maior que 1.)  Estime o consumo de tempo do seu algoritmo.
  9. Mudança de escala.  É verdade que multiplicar o custo de cada arco de um grafo por uma constante estritamente positiva não muda as soluções do problema do caminho mínimo (ou seja, que os caminhos que eram mínimos continuam mínimos)?
  10. Translação de custos.  É verdade que somar uma constante estritamente positiva ao custo de cada arco de um grafo não muda as soluções do problema do caminho mínimo (ou seja, que os caminhos que eram mínimos continuam mínimos)?
  11. ★ Suponha que os custos de todos os arcos de um grafo pertencem ao intervalo [−100, +100].  Queremos encontrar um caminho de custo mínimo que vá de um vértice s a um vértice t.  Para evitar o desconforto de lidar com números negativos, some 100 ao custo de cada arco antes de resolver o problema.  Discuta essa ideia.
  12. Distâncias em subgrafo.  Seja G um grafo com custos positivos nos arcos. Sejam s e t dois vértices de um sub­grafo induzido H de G. A distância de s a t em H é maior, igual, ou menor que a distância de st em G?
  13. Caminhos máximos.  Num grafo com custos nos arcos, um caminho C é máximo se nenhum caminho com a mesma origem e o mesmo término de C é mais caro que C.  Mostre como um algoritmo para o problema do caminho mínimo poderia ser usado para encontrar um caminho máximo de um vértice s a um vértice t.

Ciclos negativos

Num grafo com custos nos arcos, um ciclo é negativo se seu custo for negativo.  Se o grafo tem ciclos negativos, um caminho mínimo pode não ser simples.  Caso contrário, podemos supor que todo caminho mínimo é simples.

Para formular essa observação de maneira mais precisa, diremos que um ciclo C está ao alcance de um vértice s se algum vértice de C está ao alcance de s.  Temos então a seguinte

Propriedade:  Se s é um vértice sem ciclos negativos ao seu alcance, podemos supor, sem perda de generalidade, que todo caminho mínimo com origem s é simples.

A expressão podemos supor sem perda de generalidade é uma referência à possível existência de ciclos de custo nulo pendurados no caminho. Esses ciclos não afetam o custo do caminho e portanto podem ser removidos do caminho.

A seguinte propriedade também decorre da ausência de ciclos negativos:

Propriedade:  Se s é um vértice sem ciclos negativos ao seu alcance e P é um caminho mínimo com origem s então cada segmento inicial de P também é um caminho mínimo.

Graças a essas duas propriedades, o problema do caminho mínimo fica muito mais fácil quando restrito a grafos sem ciclos negativos.  Mas essa restrição levanta imediatamente a seguinte pergunta: como decidir se um grafo tem algum ciclo negativo?

Há dois casos em que a ausência de ciclos negativos é evidente: o caso em que todos os arcos têm custo positivo e o caso em que o grafo é acíclico.  Nos demais casos, não está claro como decidir se existe algum ciclo negativo. Trataremos dessa questão no capítulo Algoritmo de Bellman-Ford.

tinyEWDnc-x.png

Exemplo C.  A tabela a seguir mostra um grafo com custos nos arcos.  O caminho 4-7-5-4 é um ciclo negativo. Seu custo é -1.

0-2 0-4 1-3 2-7 3-6 4-5 4-7 5-1 5-4 5-7 6-0 6-2 6-4 7-3 7-5
 26  38  29  34  52  35  37  32 -66  28  58  40  93  39  28

Exercícios 2

  1. Seja s um vértice de um ciclo negativo. Mostre que a distância de ss é negativa.
  2. Caminhos mínimos são simples.  Seja s um vértice de um grafo e suponha que não há ciclos negativos ao alcance de s. Seja P um caminho mínimo com origem s. Mostre que alguma subsequência de P é um caminho simples com a mesma origem de P, o mesmo término de P e o mesmo custo de P.  (Essa propriedade pode ser resumida assim: se o grafo não tem ciclos negativos, podemos supor que todo caminho mínimo é simples.)  [Solução]
  3. Segmentos de caminhos mínimos são mínimos.  Prove a propriedade dos segmentos iniciais de caminhos mínimos enunciada acima.  [Solução]

Potencial e condições de minimalidade

Para provar que um dado caminho C é mínimo, precisamos mostrar que todo caminho com a mesma origem e o mesmo término que os de C é pelo menos tão caro quanto C.  Para fazer isso, usaremos uma generalização do conceito de potencial relaxado introduzido no capítulo Caminhos de comprimento mínimo.

Um potencial é uma numeração dos vértices de G, ou seja, um vetor de números indexado pelos vértices de G.  Em relação a um potencial h[ ], dizemos que um arco v-w está tenso se  h[w] − h[v]  >  c,  está relaxado se  h[w] − h[v]  ≤  c  e  está justo se  h[w] − h[v]  ≡  c,  sendo c o custo do arco.  Em outras palavras, v-w está

Um potencial é relaxado (ou viável) se todos os arcos de G estão relaxados em relação a ele.

Qualquer potencial relaxado h[ ] dá uma cota inferior para as distâncias entre vértices:  se P é um caminho de um vértice x a um vértice y então

cst(P)  ≥  h[y] − h[x],

sendo cst(P) o custo de P.  Por exemplo, [!] se P é o caminho 0-1-2-3 e cij é o custo do arco i-j então  cst(P)  =  c 23 + c 12 + c 01  ≥  h[3] − h[2] + h[2] − h[1] + h[1] − h[0]  =  h[3] − h[0].  Em particular, se P for um ciclo então cst(P) ≥ 0.  Essas considerações levam à seguinte condição suficiente de minimalidade de um caminho:

Condição suficiente de minimalidade: Para qualquer caminho C de um vértice x a um vértice y, se existe um potencial relaxado h[ ] tal que h[y] − h[x] = cst(C) então C é mínimo (e portanto a diferença h[y] − h[x] é a distância de xy).

Ao tratar dos caminhos que começam num certo vértice s, podemos nos limitar, sem qualquer prejuízo, ao sub­grafo induzido pelo conjunto de vértices que estão ao alcance de s.  Suporemos então, tacitamente, que

todos os vértices do nosso grafo estão ao alcance de s.

Isso tornará a discussão mais simples, evitando a constante repetição da frase para os vértices que estão ao alcance de s.   Adotada essa convenção simplificadora, podemos afirmar que vale então a seguinte recíproca limitada da condição suficiente:  Se o grafo não têm ciclos negativos então o vetor das distâncias a partir de s é um potencial relaxado.

figs/mine/diwheel6-k.png

Exemplo F.  Considere o grafo com custos nos arcos definido a seguir. Observe que todos os vértices estão ao alcance de 0 e que o grafo não tem ciclos negativos.

0-2 0-3 0-4 2-4 3-4 3-5 1-4 4-5 5-1 1-2
  7   2   8   1   7   1   1   0   3   3

A seguinte tabela dá um suposto vetor das distâncias a partir do vértice 0.

  v    0  1  2  3  4  5
d[v]   0  6  7  2  8  3 

O arco 1-4 não está relaxado em relação a d[]. Portanto, a tabela está errada.

figs/mine/diwheel6-k.png

Exemplo G.  Considere o grafo com custos nos arcos definido a seguir.  Observe que todos os vértices estão ao alcance de 0.

0-2 0-3 0-4 2-4 3-4 3-5 1-4 4-5 5-1 1-2
  7   2   8  -1   7   1  -1   0   3   3

Agora considere o potencial h[] definido pela tabela abaixo e verifique que o potencial é relaxado.

   v    0  1  2  3  4  5
 h[v]   0  6  7  2  5  3 

O caminho  0-3-5-1-4  tem custo 5. Como esse custo é igual à diferença h[4]-h[0], a condição suficiente de minimalidade garante que o caminho é mínimo.  (A propósito, a existência de um potencial relaxado mostra que o grafo não tem ciclos negativos. De fato, os dois únicos ciclos são 1-4-5-1 e 1-2-4-5-1 e ambos têm custo positivo.)

Exercícios 3

  1. Potencial versus ciclo negativo.  Mostre que grafos dotados de potencial relaxado não têm ciclo negativo.
  2. ★ Prove a condição suficiente de minimalidade de um caminho.
  3. ★ Prove a condição necessária de minimalidade de caminhos com origem num dado vértice:  Dado um vértice s de um grafo G, se G não têm ciclos negativos então o vetor das distâncias a partir de s é um potencial relaxado. [Solução]
  4. Considere o grafo com custos nos arcos descrito a seguir.  Verifique que o potencial h[] dado abaixo é relaxado.  Podemos concluir que h[] é o vetor das distâncias a partir de 0?  Por que?
    0-1 0-2 1-3 2-3         v   0  1  2  3
     10  10  10  10       h[v]  0  0  0  0
    
  5. Seja G um grafo com custos nos arcos, s um vértice de G, e h[] um potencial tal que h[z] ≡ INFINITY se e somente se z não está ao alcance de s. Escreva uma função que receba esses dados e decida se h[] é relaxado quando restrito ao sub­grafo induzido pelos vértices que estão ao alcance de s.
  6. Seja s um vértice de um grafo G com custos nos arcos.  Suponha que todos os vértices estão ao alcance de s. Para cada vértice v, seja h[v] o custo de algum caminho de sv. Escreva um algoritmo eficiente que receba G, s, h[] e um vértice t e decida se h[t] é a distância de st.

Árvore de caminhos baratos (CPT)

Para encontrar um caminho mínimo de um vértice s a um vértice t é inevitável calcular todos os caminhos mínimos que começam em s.  Isso sugere o seguinte conceito: uma árvore de caminhos baratos de um grafo G é uma subárvore radicada T de G tal que

  1. todos os vértices do grafo estão em T  (ou seja, T é um sub­grafo gerador)  e
  2. todo caminho em T que começa na raiz é mínimo em G.

Uma árvore de caminhos baratos também é conhecida pela abreviatura CPT de cheapest-paths tree.  (O conceito de árvore de caminhos baratos é uma generalização do conceito de árvore de caminhos curtos para grafos sem custos nos arcos.)

Um grafo tem uma CPT com raiz s se e somente se todos os vértices do grafo estão ao alcance de s e o grafo não tem ciclos negativos.  Esse fato decorre das duas propriedades enunciadas na seção Ciclos negativos acima.  Graças à convenção simplificadora adotada na seção anterior, podemos dizer que, em grafos sem ciclos negativos, o problema do caminho mínimo é equivalente ao seguinte

Problema da CPT:  Dado um vértice s de um grafo G com custos nos arcos, encontrar uma CPT de G que tenha raiz s.

Uma árvore radicada T geradora de G é uma CPT de G se e somente se as distâncias em T a partir da raiz são um potencial relaxado em G.  Essa caracterização das soluções do problema da CPT decorre imediatamente das condições necessária e suficiente da seção anterior.  Essa caracterização é o primeiro passo na direção da solução do problema.

tinyEWDn-x.png

Exemplo D.  Considere o grafo com custos nos arcos definido a seguir.

0-2 0-4 1-3 2-7 3-6 4-5 4-7 5-1 5-4 5-7  6-0  6-2  6-4 7-3 7-5
 26  38  29  34  52  35  37  32  35  28 -140 -120 -125  39  28

A figura mostra uma sub­árvore radicada T com raiz 0. A seguinte tabela dá o vetor h[] das distâncias em T a partir de 0

  v    0   1   2   3   4   5   6   7  
h[v]   0  93  26  99  26  61 151  60

Verifique que h[] é um potencial relaxado no grafo. Portanto, T é uma CPT.  (A propósito, a existência de um potencial relaxado garante que o grafo não tem ciclos negativos.)

Exercícios 4

  1. Mostre que um grafo pode ter mais de uma CPT com uma dada raiz s.  (Por isso dizemos uma CPT e não a CPT.)
  2. Dê um exemplo de um grafo que não tem CPT. (É claro que o grafo deve ter algum ciclo negativo.)
  3. ★ Prove o fato enunciado acima sobre a relação entre ciclos negativos e CPT.  (Sugestão: veja a relação entre ciclos negativos e caminhos simples e a relação entre ciclos negativos e segmentos de caminhos mínimos.)
  4. Seja T uma árvore radicada num grafo G com custos nos arcos. Seja s a raiz de T. Para cada vértice v de T, seja h[v] a distância de sv em T. Mostre que todos os arcos de T (eu disse de T) estão relaxados em relação a h[ ].
  5. Condição suficiente para CPT.  Seja T uma árvore radicada geradora de um grafo G com custos nos arcos. Seja s a raiz de T e h[ ] o vetor das distâncias em T a partir de s. Suponha que h[ ] é um potencial relaxado em G e prove que T é uma CPT.
  6. Condição necessária para CPT.  Seja T uma CPT de um grafo G com custos nos arcos. Seja s a raiz de T e h[ ] o vetor das distâncias em T a partir de s. Prove que h[ ] é um potencial relaxado em G.
  7. Verifique que potencial h[] do exemplo D é relaxado.
  8. Considere o grafo com custos nos arcos definido abaixo. O vetor de pais pa[] define uma árvore radicada com raiz 0. O vetor h[] registra os custos dos caminhos na árvore que começam em 0.  Essa árvore é uma CPT?
    0-2 0-3 0-4 2-4 3-4 3-5 1-4 4-5 5-1 1-2
      7   2   8   1   7   1   1   0   3   3
    
       v    0  1  2  3  4  5
    pa[v]   0  5  0  0  0  3
     h[v]   0  6  7  2  8  3 
    
  9. Considere o grafo com custos nos arcos definido a seguir. Veja logo abaixo o vetor de pais de uma árvore radicada T com raiz 0 e, para cada vértice v, o custo h[v] do único caminho de 0v em T.  Essa árvore é uma CPT?
    0-1 1-2 2-3 4-3 3-5 3-0 0-5 5-4 1-4 4-2 5-1 
     41  51  50  36  38  45  29  21  32  32  29 
    
       v    0  1  2  3  4  5
    pa[v]   0  0  4  4  5  0
     h[v]   0 41 82 86 50 29
    
  10. Verificação de CPT.  Escreva uma função que receba um grafo G com custos nos arcos e uma árvore radicada T em G e diga se T é uma CPT de G. Suponha que T é dada por um vetor de pais pa[] junto com um vetor c[] tal que c[v] é o custo do arco pa[v]-v sempre que pa[v] está definido e é diferente de v.
  11. Seja s um vértice e v-w um arco de custo mínimo num grafo G. É verdade que v-w pertence a alguma CPT com raiz s?
  12. Árvore convergente?  Por que não estudar o conceito análogo a CPT em que todos os caminhos terminam na raiz t?
  13. CPT versus MST.  Seja T uma CPT com raiz s em um grafo não-dirigido com custos positivos nas arestas.  É verdade que T é também uma MST (árvore geradora de custo mínimo)?  Suponha agora que T é uma MST e seja s um dos vértices de T.  É verdade que T é uma CPT com raiz s?

Algoritmos

Não se conhece um algoritmo rápido (mais precisamente, um algoritmo polinomial) para o problema do caminho de custo mínimo.  Entretanto, existem algoritmos razoávelmente rápidos para a restrição do problema a grafos que não têm ciclo negativoEm particular, existem algoritmos razoavelmente rápidos para o problema da CPT.  Todos calculam um vetor de pais pa[] e o correspondente vetor das distâncias dist[] aplicando a operação de relaxação

   if (dist[v] + cvw < dist[w]) {
       dist[w] = dist[v] + cvw;
       pa[w] = v;
   }

a cada arco v-w de custo cvw.  Quando todos os arcos estiverem relaxados, pa[] será o vetor de pais de uma CPT, conforme a condição suficiente da seção Potencial e condições de minimalidade acima.  Se for impossível relaxar todos os arcos, o algoritmo conclui que o grafo tem um ciclo negativo e portanto não tem CPT.

Os capítulos seguintes discutem três algoritmos para o problema da CPT:

Exercícios 5

  1. Análise de sensibilidade.  Suponha dado um grafo G com custos nos arcos, um vértice s, e a distância dist[v] de sv para cada vértice v.  Decida se é possível diminuir o custo de um dado arco v-w sem que as distâncias a partir de s sofram alterações.
  2. Análise de sensibilidade.  Suponha dado um grafo G com custos nos arcos, um vértice s, e a distância dist[v] de sv para cada vértice v.  Decida se épossível aumentar o custo de um dado arco v-w sem que as distâncias a partir de s sofram alterações.
  3. Custos nos vértices.  Suponha dado um grafo com custos nos vértices. O custo de um caminho num tal grafo é a soma dos custos dos vértices do caminho. Queremos encontrar um caminho mínimo de um dado vértice s a um dado vértice t.  Reduza esse problema ao problema do caminho de custo mínimo.  (Sugestão: troque cada vértice v com custo c por um arco v'-v'' com custo c. Os arcos que entravam em v passam a entrar em v' e os que saíam de v passam a sair de v''.)

Perguntas e respostas