Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Problemas em DAGs

Muitos problemas básicos sobre digrafos admitem solução bem mais eficiente se restringirmos nosso universo aos DAGs (ou melhor, a digrafos dotados de ordenação topológica).  Frequentemente as soluções usam algoritmos de programação dinâmica (veja os apontadores para "programação dinâmica" na página Análise de Algoritmos).

(Esta página corresponde aproximadamente à seção 19.6 (Topological Sorting) do capítulo 19 (Digraphs and DAGs), p.183-193, do livro de Sedgewick.)

Caminhos mínimos em DAGs

Suponha que G é um DAG com custos não negativos nos arcos. Sejam s e t dois vértices de G. Para encontrar um caminho de custo mínimo de s a t, podemos usar o algoritmo de Dijkstra, que ignora o caráter acíclico de G. Esse algoritmo consome tempo proporcional a (V+A) log(V) no pior caso (e é, portanto, um pouco pior que linear).   Se tirarmos proveito do caráter acíclico de G, é possível resolver o problema em tempo linear, ou seja, tempo limitado por

V + A

no pior caso.  A função abaixo faz isso.  Se não existe caminho algum de s a t, a função devolve um número maxCOST que faz o papel de ∞.

/* A função DAGmin recebe um DAG G com custos não negativos nos arcos e uma ordenação topológica ts de G. Recebe também um vértice s.  Para cada vértice t, a função calcula o custo de um caminho de custo mínimo de s a t.  Esse número é depositado em cost[t]. */

/* A função supõe que a soma dos custos de todos os arcos é estritamente menor que maxCOST.  (O código é uma versão modificada do programa 21.6, p.304, Sedgewick.) */

void DAGmin (Digraph G, Vertex ts[], Vertex s, double cost[]) { 
   int i; Vertex v; link p;
   for (v = 0; v < G->V; v++)
      cost[v] = maxCOST;
   cost[s] = 0.0;
   for (v = ts[i = 0]; i < G->V; v = ts[i++])
      for (p = G->adj[v]; p != NULL; p = p->next) 
         if (cost[p->w] > cost[v] + p->cost) 
            cost[p->w] = cost[v] + p->cost; 
}

Exercícios

1. A varredura dos vértices em DAGmin não precisa começar com v = 0;  bastaria começar com v = s.  Escreva uma versão de DAGmin que faça isso.
2. Modifique o código de DAGmin para que a função calcule uma SPT com raiz s.
3. [Custos arbitrários]  Mostre que DAGmin pode ser usada com custos arbitrários (positivos, negativos, nulos), desde que o vetor cost seja inicializado de maneira apropriada.
4. Na função DAGmin, é mais eficiente calcular os caminhos mínimos ao mesmo tempo que se calcula a ordenação topológica. Escreva o código correspondente.

Caminhos máximos em DAGs

Do ponto de vista computacional, o problema de encontrar um caminho simples de custo máximo num digrafos com custos nos arcos é difícil.  O problema torna-se fácil, entretanto, quando restrito a DAGs.

Dados vértices s e t de um DAG com custos não negativos nos arcos, considere o problema de encontrar um caminho simples de custo máximo de s a t.  (Na verdade, o requisito "simpes" é redundante, pois todos os caminhos num DAG são simples.) A função abaixo resolve o problema.  Compare o código com o de DAGmin.

/* A função DAGmax recebe um DAG G com custos não negativos nos arcos e uma ordenação topológica ts de G. Recebe também um vértice s.  Para cada vértice t, a função calcula o custo de um caminho de custo máximo de s a t.  Esse número é depositado em cost[t]. */

/* A função supõe que a soma dos custos de todos os arcos é estritamente menor que maxCOST.  (O código é uma versão modificada do programa 21.6, p.304, Sedgewick, que define a função DIGRAPHlpt.) */

void DAGmax (Digraph G, Vertex ts[], Vertex s, double cost[]) { 
   int i; Vertex v; link p;
   for (v = 0; v < G->V; v++)
      cost[v] = -maxCOST;
   cost[s] = 0.0;
   for (v = ts[i = 0]; i < G->V; v = ts[i++])
      for (p = G->adj[v]; p != NULL; p = p->next) 
         if (cost[p->w] < cost[v] + p->cost) { 
            cost[p->w] = cost[v] + p->cost; 
}

Exercícios

5. Que acontece se trocarmos a inicialização  "cost[v] = -maxCOST"  em DAGmax por  "cost[v] = -1"?
6. A varredura dos vértices em DAGmax não precisa começar com v = 0;  bastaria começar com v = s.  Escreva uma versão de DAGmax que faça isso.
7. Modifique o código de DAGmax para que a função calcule os caminhos de custo máximo e não só os seus custos.
8. [Custos arbitrários]  Mostre que DAGmax pode ser usada com custos arbitrários, desde que o vetor cost seja inicializado de maneira apropriada.
9. Na função DAGmax, é mais eficiente calcular os caminhos máximos ao mesmo tempo que a ordenação topológica. Escreva o código correspondente.
10. [PERT]  O seguinte problema surge naturalmente na administração de grandes projetos de engenharia.  Dado um DAG com custos não negativos nos arcos, encontrar um caminho de custo máximo, quaisquer que sejam sua origem e seu término. (Um tal caminho necessariamente começa numa fonte e termina num sorvedouro.)  Adapte o código de DAGmax para resolver o problema.
11. Escreva um programa que encontre um caminho máximo num DAG sem custos nas arcos. (Um tal caminho necessariamente começa numa fonte e termina num sorvedouro.)  O consumo de tempo do seu programa deve ser proporcional a V no máximo.
12. Seja G um DAG sem custos nos arcos e suponha que a permutação identidade  0,1,..,V-1  é uma ordem topológica dos vértices de G. A seguinte função promete devolver o comprimento de um caminho máximo em G. Ela está correta?

       int maxpath (Digraph G) {
          Vertex v;
          link p;
          int cost[maxV], x = 0;
          for (v = 0; v < G->V; v++) cost[v] = 0;
          for (v = 0; v < G->V; v++) 
             for (p = G->adj[v]; p != NULL; p = p->next) {
                cost[p->w] = cost[v] + 1;
                if (x < cost[p->w]) x = cost[p->w];
             }
          return x;
       }