Algoritmos para Grafos  |  Índice

Fluxo máximo via caminhos aumentadores de máxima capacidade

Este capítulo descreve a camada interna da função que implementa o algoritmo de Ford-Fulkerson.  Essa camada interna consiste na função AugmPath(), que tem a missão de calcular um caminho aumentador num grafo expandido. A versão de AugmPath() discutida neste capítulo produz um caminho aumentador 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.

Caminho aumentador de máxima capacidade residual

A versão MaxCapAugmPath() da função AugmPath() calcula um caminho aumentador que tenha capacidade residual máxima.  (Essa ideia foi sugerida, em 1972, por Edmonds e Karp.)  A função recebe um grafo capacitado G e um fluxo com vértice inicial s e vértice final t. O grafo é representado por listas de adjacência com nós expandidos. Cada nó expandido representa um arco do grafo que tem uma certa capacidade cap e carrega um certo fluxo flow que respeita a capacidade embora possa ser negativo em alguns arcos.

Alguns arcos de G são originais enquanto outros são artificiais, mas a função ignora essa distinção (em particular, ignora os campos type e twin dos nós) e toma conhecimento apenas da capacidade residual cap - flow de cada arco (essa capacidade residual é positiva). A função limita-se a calcular um caminho de s a t que tenha a maior capacidade residual possível. O caminho é armazenado no par de vetores pa[] e parc[].  (Os nomes dos vetores são abreviaturas de parent e parent arc respectivamente.)

A função MaxCapAugmPath() usa ideias análogas às de preço e gancho da implementação GRAPHcptD2() do algoritmo de Dijkstra.  O código usa uma fila priorizada (= priority queue) de máximo análoga à fila priorizada de mínimo que empregamos em outras ocasiões.  A fila é manipulada pelas funções PQinit(), PQinsert(), PQinc(), PQempty() e PQdelmax(). A prioridade de um vértice v é cprd[v].  A função PQdelmax() retira da fila um vértice com prioridade máxima. A função PQinc() reorganiza a fila depois de um aumento no valor de cprd[v].

No início de cada iteração, para cada vértice x fora da árvore radicada definida por pa[] e parc[], o número cprd[x] é a maior capacidade residual que é possivel levar de s até x, ou seja, a capacidade residual de um caminho de capacidade residual máxima dentre os que começam em s, terminam em x, e têm um só vértice (o último) fora da árvore radicada.

/*  Esta é a versão MaxCapAugmPath() 
da função AugmPath(). */

#define AugmPath MaxCapAugmPath

/* Recebe um grafo capacitado G e um fluxo 
   registrado nos campos flow dos nós das listas de adjacência.
   Calcula um caminho de capacidade residual máxima
   de s a t 
   e armazena o caminho nos vetores pa[] e parc[].
   Devolve a capacidade residual do caminho ou devolve 0
   se tal caminho não existe.
   A função supõe que todas as capacidades são menores 
   que uma constante M. */

int MaxCapAugmPath( Graph G, vertex s, vertex t,
                    vertex pa[], link parc[]) 
{ 
   int cprd[1000];
   PQinit( G->V); 
   for (vertex x = 0; x < G->V; ++x)
      cprd[x] = 0, PQinsert( x, cprd); 
   cprd[s] = M; 
   PQinc( s, cprd); 

   while (!PQempty( )) {
      vertex x = PQdelmax( cprd);
      if (cprd[x] == 0 || x == t) break;
      for (link a = G->adj[x]; a != NULL; a = a->next) {
         // a pode ser original ou artificial
         int residual = min( cprd[x], a->c - a->flow);
         if (residual > cprd[a->w]) { 
            cprd[a->w] = residual; 
            pa[a->w] = x, parc[a->w] = a; 
            PQinc( a->w, cprd); 
         }
      }
   }
   PQfree( );
   return cprd[t];
}

Exemplo A.  Considere o grafo capacitado abaixo (mesmo do exemplo B discutido para ShrtAugmPath()). Os vértices inicial e final são 0 e 13 respectivamente. Aplique a função GRAPHmaxFlow(), combinada com a função MaxCapAugmPath() ao grafo, começando com fluxo nulo.

        arco     cap 
         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 função GRAPHmaxFlow() combinada com MaxCapAugmPath() produz a seguinte sequência de caminhos aumentadores a partir do fluxo nulo. Os arcos artificiais estão indicados em vermelho. (Mas MaxCapAugmPath() ignora a distinção entre arcos artificiais e originais.)  Cada caminho aumentador tem capacidade residual máxima. A capacidade residual de cada caminho está registrada na segunda coluna.

caminho              delta
0-1-5-12-10-13       6  
0-3-5=1-7-13         3  
0-3-10-13            3  
0-2-9-13             3  
0-4-11-13            3  
0-3-8-9-13           3  
0-1-6-11-13          3  
0-4-6-7-13           3  
0-2-8-10=12-7-13     3  

O fluxo final tem intensidade 30.

Número de iterações do algoritmo de fluxo máximo

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