Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Algoritmo de fluxo máximo:
versão maximum capacity augmenting paths

Esta página descreve uma implementação do algoritmo dos caminhos de aumento que usa caminhos de aumento de capacidade residual máxima.  O consumo de tempo dessa implementação depende apenas do logaritmo das capacidades dos arcos, ao contrário do que acontece com a versão genérica do algoritmo.

[Esta página é um resumo da segunda parte da seção 22.2 (Augmenting-Path Maxflow Algorithms) do livro de Sedgewick.]

Camada externa da implementação

A camada externa da implementação é idêntica à da implementação anterior.

/* Calcula um fluxo máximo na rede capacitada G. O fluxo é armazenado na estrutura de G. */

/* (Esse código foi copiado da segunda parte do programa 22.3, p.378, de Sedgewick.) */

void MaxFlow (Flownet G) { 
   Vertex s = G->s, t = G->t, x; 
   int d; link parent[maxV]; 
   Expand(G);
   while (1) {
      d = AugmentingPath(G, parent);
      if (d == 0) break;
      for (x = t; x != s; x = parent[x]->dup->w) { 
         parent[x]->flow += d; 
         parent[x]->dup->flow -= d; 
      }
   }
}

A função AugmentingPath procura um caminho de aumento na rede de fluxo expandida e devolve a capacidade residual desse caminho. Se não existe caminho de aumento, a função deve devolver 0. Senão, o caminho é armazenado no vetor parent.

Maximum-capacity augmenting paths

A versão de AugmentingPath que descrevemos a seguir procura um caminho de aumento que tenha capacidade residual máxima.  Essa ideia foi sugerida, em 1972, por Edmonds e Karp.

Para encontrar um caminho de aumento que tenha capacidade residual máxima, basta usar uma variante do algoritmo de Dijkstra. (Veja especialmente a função DIGRAPHsptD3.)

Nossa implementação usa uma fila-com-prioridades manipulada pelas funções PQinit, PQinsert, PQinc, PQempty e PQdelmax. A prioridade de um vértice v é rc[v]. A função PQdelmax retira da fila um vértice de prioridade máxima. A função PQinc reorganiza a fila depois de um aumento no valor de rc[v].

No início de cada iteração, para cada vértice w fora da arborescência definida por parent, o número rc[w] é a capacidade residual de um caminho dirigido de capacidade residual máxima dentre os que começam em s, terminam em w, e têm um só vértice (o último) fora da arborescência.

/* (Este código é uma versão melhorada do programa 22.3, p.378, de Sedgewick.) */

#define MaxCapAugmPath AugmentingPath
static int rc[maxV];

/* A macro RC recebe um link L e calcula a capacidade residual do arco da rede de fluxo expandida que vai do vértice L->dup->w ao vértice L->w. */

#define RC(L) (L->cap >= 0 ? L->cap - L->flow : -L->flow)

/* A função MaxCapAugmPath devolve 0 se não há caminho de aumento. Caso contrário, devolve a capacidade residual de um caminho de aumento na rede de fluxo expandida e armazena o caminho no vetor parent. A função supõe que todas as capacidades são menores que M. */

int MaxCapAugmPath (Flownet G, link parent[]) { 
   Vertex s = G->s, t = G->t, v, w;
   link p; int d;
   PQinit(); 
   for (v = 0; v < G->V; v++) { 
      rc[v] = 0; 
      PQinsert(v); 
   }
   rc[s] = M; 
   PQinc(s); 
   while (!PQempty()) {
      v = PQdelmax();
      if (rc[v] == 0 || v == t) break;
      for (p = G->adj[v]; p != NULL; p = p->next) {
         if (RC(p) > 0) {
            int min = (RC(p) < rc[v] ? RC(p) : rc[v]);
            w = p->w;
            if (rc[w] < min) { 
               rc[w] = min; 
               PQinc(w); 
               parent[w] = p; 
            }
         }
      }
      rc[v] = M;
   }
   if (rc[t] == 0) return 0; 
   d = M;
   for (w = t; w != s; w = parent[w]->dup->w) { 
      p = parent[w]; 
      if (d > RC(p)) d = RC(p); 
   }
   return d;
}

Exemplo

Aplique a função MaxFlow à rede capacitada da figura:

        arco     cap   s=0  t=13
         0-1     9
         0-2     6
         0-3     9
         0-4     6
         1-5     7
         1-6     3
         1-7     3
         2-3     2
         2-8     3
         2-9     3
         3-5     7
         3-8     3
         3-10    3
         4-1     2
         4-6     3
         4-11    3
         5-12    6
         6-7     5
         6-11    3
         7-13    9
         8-9     3
         8-10    5
         9-13    6 
        10-13    9
        11-13    6
        12-7     7
        12-10    7

(A rede é a mesma do exemplo discutido quando estudamos a versão shortest augmenting path de MaxFlow. Veja figura 22.19, p.381, de Sedgewick.)

Exercícios

1. Na função MaxCapAugmPath, a busca por um caminho de aumento é interrompida tão logo o vértice t é atingido. Se deixarmos o processso iterativo continuar até que a fila fique vazia, poderíamos encontrar um caminho até t com capacidade residual maior?  Isso é possível?
2. Que acontece se eliminarmos a linha "rc[v] = M" do código de MaxCapAugmPath?
3. Mostre que a capacidade residual do caminho de aumento encontrado por MaxCapAugmPath é, de fato, máxima.

Número de iterações

O consumo de tempo da função MaxFlow é proporcional ao número de iterações e portanto ao número de caminhos de aumento necessários para atingir o fluxo máximo.  Quantos caminhos são necessários, no pior caso?

Número de Caminhos de Aumento (Property 22.8, p.387, Sedgewick):  O número de caminhos de aumento usados pela função MaxFlow associada à MaxCapAugmPath nunca é maior que  2A log(M),  sendo A o número de arcos originais e M a maior das capacidades.