Algoritmos para Grafos  |  Índice

Caminhos baratos em dags

Este capítulo trata de um algoritmo muito eficiente para o problema da árvore de caminhos de custo mínimo restrito a dags (grafos acíclicos). Uma introdução geral ao problema foi dada no capítulo Caminhos de custo mínimo.

Vale lembrar que uma árvore de caminhos baratos, ou CPT (= cheapest-paths tree), é uma sub­árvore radicada geradora T de G tal que todo caminho em T que começa na raiz tem custo mínimo em G.  Como observamos no capítulo introdutório, um dag tem uma CPT com raiz s se e somente se todos os seus vértices estão ao alcance de s.  Para escamotear essa condição, podemos trabalhar com o sub­grafo induzido pelos vértices que estão ao alcance de s.

Algoritmo

Como se sabe, um grafo é um dag se e somente se admite uma permutação topológica do seu conjunto de vértices.  A permutação topológica permite processar o dag de modo simples e eficiente.

Ao receber um dag G com custos nos arcos e um vértice s, o algoritmo deveria produzir uma CPT de G com raiz s ou informar que uma tal CPT não existe.  Para simplificar as coisas, tomaremos duas decisões de projeto: (1) suporemos que todos os vértices de G estão ao alcance de s e (2) suporemos dada uma permutação topológica, digamos vv[0..V-1], dos vértices.  Em virtude de (1), temos vv[0] ≡ s.

A função DAGcpt() a seguir é uma generalização óbvia de DAGspt() do capítulo Caminhos de comprimento mínimo.  Suporemos que o dag G é representado por listas de adjacência com custos.  Assim, para cada vértice v e cada a em G->adj[v], o arco que vai de v a a->w tem custo  a->c.

#define Dag Graph

/* Esta função recebe um dag G 
   com custos nos arcos,
   uma permutação topológica vv[] 
   de G,
   e um vértice s de G.
   Supõe que todos os vértices estão ao alcance de s.
   A função calcula e armazena em pa[]
   o vetor de pais de uma CPT de G com raiz s.
   As distâncias a partir de s
   são armazenadas no vetor dist[].

   (O código foi inspirado no programa 21.6
   de Sedgewick.) */

void DAGcpt( Dag G, vertex *vv, vertex s,
             vertex *pa, int *dist) 
{ 
   for (vertex v = 0; v < G->V; ++v)
      pa[v] = -1, dist[v] = INT_MAX;

   pa[s] = s, dist[s] = 0;
   for (int j = 0; j < G->V; ++j) {
      vertex v = vv[j];
      if (dist[v] == INT_MAX) continue;
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         if (dist[v] + a->c < dist[a->w]) {
            dist[a->w] = dist[v] + a->c; 
            pa[a->w] = v;
         }
      }
   }
}

Algumas observações podem ajudar a entender o código:

• A função verifica explicitamente o estado de relaxação de cada arco em relação ao potencial dist[]. Todo arco v-w de custo c que estiver tenso é submetido à operação de relaxação dist[w] = dist[v] + c, que diminui o valor de dist[w]. Para cada vértice w, o valor de dist[w] pode diminuir várias vezes durante a execução da função.
• A relaxação dos arcos que saem de vv[j] não afeta os vértices vv[0..j-1], que já foram processados, uma vez que todos os vizinhos de vv[j] estão em vv[j+1...].
• A constante INT_MAX representa o infinito. A função supõe, tacitamente, que o valor da expressão dist[v] + a->c é sempre menor que INT_MAX. Para garantir isso, basta que a soma de todos os custos positivos do dag seja menor que INT_MAX. Convém certificar-se também de que a soma de todos os custos negativos é maior que INT_MIN, garantindo assim que não teremos overflow aritmético.
• O método usado pela função é um exemplo de programação dinâmica.

A função supõe que todos os vértices estão ao alcance de s. Mas não é necessário testar essa condição antes de invocar a função: Se a condição não estiver satisfeita, a função produzirá uma CPT no sub­grafo induzido pelo conjunto de vértices que estão ao alcance de s.

Exemplo A.  Considere o dag definidos pelos arcos e custos abaixo.  Observe que a sequência  0 1 2 3 4 5  é uma permutação topológica dos vértices.

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

Queremos calcular uma CPT com raiz 0.  Invoque a função DAGcpt() com parâmetro s igual a 0. Veja o estado dos vetores dist[] e pa[] no início de sucessivas iterações (com * representando INT_MAX):

           dist[]               pa[]       
j vv[j]    0  1  2  3  4  5     0 1 2 3 4 5
                                           
0   0      0  *  *  *  *  *     0 - - - - -
1   1      0 10 10  *  *  *     0 0 0 - - -
2   2      0 10 10 20 20  *     0 0 0 1 1 -
3   3      0 10 10 20 20  *     0 0 0 1 1 -
4   4      0 10 10 20 20 40     0 0 0 1 1 3
5   5      0 10 10 20 20 30     0 0 0 1 1 4
6          0 10 10 20 20 30     0 0 0 1 1 4

Agora, pa[] representa uma CPT com raiz 0.

Exemplo B.  Considere o dag definidos pelos arcos e custos abaixo.  Observe que a sequência  0 1 2 3 4 5  é uma permutação topológica dos vértices.

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

Queremos calcular as distâncias a partir do vértice 2, embora nem todos os vértices estejam ao alcance de 2.  Invoque a função DAGcpt() com parâmetro s igual a 2 e veja o estado dos vetores dist[] e pa[] no início de sucessivas iterações (com * representando INT_MAX):

           dist[]               pa[]       
j vv[j]    0  1  2  3  4  5     0 1 2 3 4 5
                                           
0   0      *  *  0  *  *  *     - - 2 - - -
1   1      *  *  0  *  *  *     - - 2 - - -
2   2      *  *  0  *  *  *     - - 2 - - -
3   3      *  *  0 10 10  *     - - 2 2 2 -
4   4      *  *  0 10 10 30     - - 2 2 2 3
5   5      *  *  0 10 10 20     - - 2 2 2 4
6          *  *  0 10 10 20     - - 2 2 2 4

Agora, pa[] representa uma CPT com raiz 2 no sub­grafo induzido pelo conjunto de vértices que estão ao alcance de 2.

Análise

Para verificar que a função DAGcpt() está correta, basta observar que os seguintes invariantes valem no início de cada iteração:

1. o vetor pa[] define uma árvore radicada, digamos T, com raiz s;
2. para todo vértice x de G, dist[x] é a distância de s a x em T ;
3. para todo arco x-y de G, se x está em vv[0..j-1] então x-y está relaxado em relação a dist[].

(Segue imediatamente do invariante ii que dist[x] vale INT_MAX se e somente se x não está em T.)

Agora considere a última iteração, que começa com j ≡ G->V e termina imediatamente.  Em virtude do invariante iii, dist[] é um potencial relaxado em G.  Em virtude dos invariantes i e ii, T é uma árvore radicada em G e dist[] é o vetor das distâncias em T a partir de s.

Resta apenas provar que T é geradora.  Para isso, basta mostrar que não existe arco de G com ponta inicial em T e ponta final fora de T.  Tome um arco qualquer x-y de G tal que x pertence a T. Como x-y está relaxado, dist[y] ≤ dist[x] + 1. Graças ao invariante ii, dist[x] < INT_MAX. Segue daí que dist[y] < INT_MAX e portanto y está em T. Isso mostra que T contém todos os vértices que estão ao alcance de s em G, e portanto todos os vértices de G.  Concluímos assim que os caminhos em T a partir de s satisfazem a condição suficiente de minimalidade (veja a seção Potencial e condições de minimalidade do capítulo Caminhos de custo mínimo). Portanto T é uma CPT de G.

Desempenho.  A função DAGcpt() examina cada arco do dag uma única vez.  Assim, o consumo de 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.  Remumindo: a função DAGcpt() é linear.