Algoritmos para Grafos  |  Índice

Caminhos simples de custo máximo

Este capítulo é uma introdução geral ao difícil e traiçoeiro problema dos caminhos simples de custo máximo em grafos com custos nos arcos.

Vamos supor que os custos de todos os arcos são positivos, embora a maior parte dos conceitos e observações deste capítulo façam sentido com custos arbitrários.

O problema

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.

Um caminho D é mais caro que um caminho C se tiver custo maior que o de C.  Dizemos que um caminho C  tem custo máximo  se nenhum caminho com a mesma origem e o mesmo término que C for mais caro que C. 

A qualificação simples não é redundante nesse problema, diferentemente do que acontece com caminhos de custo mínimo.  O problema tem solução se e somente se t está ao alcance de s.  A propósito, se s ≡ t então a única solução do problema é o caminho trivial de comprimento 0.

Um caso particular célebre do problema é o do caminho hamiltoniano:  encontrar um caminho simples de s a t que passe por todos os vértices do grafo.  (Quanto ao problema do ciclo hamiltoniano, ele não é um caso particular do nosso problema pois sua solução tem um vértice repetido.)

Exemplo A.  Considere o grafo (não-dirigido) definido pelo conjunto de arcos abaixo. Suponha que todos os arcos têm custo 1. Um caminho simples de custo máximo do vértice 0 ao vértice 2 tem custo 4.

0-1 1-0 1-2 2-1 0-3 3-0 1-3 3-1 1-4 4-1 2-4 4-2

   2   
   |   
0--1--3

Exemplo B.  Considere o grafo (não-dirigido) definido pelo conjunto de arcos abaixo. Suponha que todos os arcos têm custo 1. Um caminho simples de custo máximo do vértice 0 ao vértice 3 tem custo 2.

0-1 1-0 1-2 2-1 1-3 3-1

Exemplo C.  Considere o grafo definido pelo conjunto de arcos abaixo. Suponha que todos os arcos têm custo 1. Um caminho simples de custo máximo do vértice 0 ao vértice 4 tem custo 2.  (Note que há um caminho de 0 a 4 que tem custo 5.)

0-1 1-2 2-3 3-1 1-4

Um algoritmo para dags

Quando restrito a dags, o problema do caminho simples de custo máximo é fácil.  Em um dag, todos os caminhos são simples e portanto o problema pode ser reformulado assim:

A função DAGcpt() do capítulo Caminhos baratos em dags pode ser usada para resolver o problema:  basta inverter o sinal de todos os custos!  Outra possibilidade é deixar os custos inalterados e trocar INT_MAX e dist[v]+a->c < dist[a->w] por INT_MIN e dist[v]+a->c > dist[a->w], respectivamente, no código de DAGcpt().  Essas duas variantes de DAGcpt() são muito eficientes:  consomem tempo proporcional a V + A no pior caso, sendo V o número de vértices e A o número de arcos do dag.

Algoritmo de força bruta

O problema do caminho simples de custo máximo é difícil. Parte da dificuldade está na exigência de que os caminhos sejam simples. Mas a maior dificuldade decorre da exigência de custo máximo.  Nenhum algoritmo razoavelmente rápido foi encontrado ainda.

O problema não fica mais fácil se todos os arcos tiverem custo 1.  Também não fica mais fácil se restrito a grafos não-dirigidos.

Examinaremos a seguir um algoritmo de força bruta que calcula o custo de um caminho simples de custo máximo de s a t (embora não exiba o caminho propriamente dito).  O algoritmo é extremamente lento. pois examina todos os caminhos simples de s a t. Embora a ideia seja simplória, o código não é inteiramente óbvio.

static bool mark[1000];

/* Recebe um grafo G com custos positivos nos arcos
   e vértices s e t.
   Devolve o custo de um caminho simples de custo máximo
   de s a t.
   (Em particular, devolve 0 se s == t.)
   Se não existe caminho algum de s a t,
   devolve -1 (que representa infinito negativo).
   Cuidado! Esta função só é razoável para grafos muito pequenos.
   (O código foi inspirado no programa 17.12 
   de Sedgewick.) */ 

int GRAPHmaxCostPath( Graph G, vertex s, vertex t)
{
   for (vertex v = 0; v < G->V; ++v) 
      mark[v] = false;
   return dfsRmaxCostPath( G, s, t);
}

/* Esta função recebe um grafo G
   com custos positivos nos arcos, um conjunto de vértices marcados, 
   e vértices não marcados v e t
   (possivelmente iguais). A função examina o conjunto, digamos C, 
   de todos os caminhos simples de v a t
   que não têm vértices marcados.
   Se C é vazio, devolve -1.
   Senão, devolve o custo do caminho mais caro de C.
   (Em particular, devolve 0 se v == t.) 
   A função não altera o conjunto de vértice marcados. */

static int dfsRmaxCostPath( Graph G, vertex v, vertex t)
{
   if (v == t) 
      return 0;
   mark[v] = true;
   int m = -1;
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      if (!mark[a->w]) {
         int mw = dfsRmaxCostPath( G, a->w, t);
         if (mw != -1 && a->c + mw > m) 
            m = a->c + mw;
      }
   }
   mark[v] = false; // atenção! backtrack
   return m;
}

Esse algoritmo usa uma variante da busca em profundidade conhecida como backtracking. A única diferença com relação ao código da busca em profundidade usual (veja o capítulo Acessibilidade) está na penúltima linha de dfsRmaxCostPath(), que desmarca o vértice v restaurando o valor original de mark[v]. Isso garante que todos os caminhos simples sejam examinados.

Desempenho.  O algoritmo examina todos os caminhos simples de s a t. Isso equivale, no pior caso, a examinar todas as permutações dos vértices do grafo. Um grafo com V vértices tem V ! tais permutações, e esse número é bem maior que 2^V. Assim, o consumo de tempo de GRAPHmaxCostPath() cresce mais que exponencialmente com o tamanho do grafo. Portanto, o algoritmo só pode ser aplicado a grafos muito pequenos.