Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página descreve uma implementação do algoritmo dos caminhos de aumento que usa caminhos de aumento com número mínimo de arcos. O consumo de tempo dessa implementação não depende das capacidades dos arcos, ao contrário do que acontece com a versão genérica do algoritmo.
(Esta página é um resumo de parte da seção 22.2 (Augmenting-Path Maxflow Algorithms) do livro de Sedgewick.)
Como vimos, um caminho de aumento pode ser representado por um caminho (dirigido) de capacidade residual positiva na correspondente rede de fluxo expandida. Para encontrar um tal caminho, podemos usar o algoritmo de busca em largura como modelo. Nossa implementação daquele algoritmo usou um vetor de pais parent: sempre que percorria um arco v-w, a implementação fazia parent[w] = v. No código abaixo, o vetor parent será usado de maneira um pouco diferente: ao percorrer um arco v-w da rede de fluxo expandida, o código fará
parent[w] = p ,
sendo p o endereço do nó na lista adj[v] para o qual p->w vale w. (Podemos dizer, informalmente, que p é um arco que entra em w.) O "pai" v de w será então parent[w]->dup->w.
Podemos agora escrever assim a "camada externa" da implementação do algoritmo dos caminhos de aumento (essa camada é comum a todas as implementações do algoritmo):
/* Recebe uma rede capacitada (não expandida) G e calcula um fluxo máximo na rede. A função armazena o fluxo máximo na estrutura de G. O código supõe que G tem no máximo maxV vértices. */
/* (O 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 tem a missão de encontrar um caminho de aumento na rede de fluxo expandida e devolver 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 da maneira indicada acima.
A versão da função AugmentingPath que descrevemos as seguir procura por um caminho de aumento com o menor número possível de arcos. Essa ideia foi sugerida, em 1972, por Edmonds e Karp.
Para encontrar um caminho de aumento que tenha número mínimo de arcos, basta aplicar o algoritmo de busca em largura à rede de fluxo expandida. É o que faremos abaixo. O processo de busca em largura usa uma fila de vértices, manipulada pelas funções QUEUEinit, QUEUEempty, QUEUEput e QUEUEget.
/* Esta é uma implementação shortest-augmenting-path da função AugmentingPath. O código foi inspirado no programa 22.3, p.378, de Sedgewick. */
#define ShrtstAugmPath AugmentingPath/* 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 ShrtstAugmPath 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 ShrtstAugmPath (Flownet G, link parent[]) { Vertex s = G->s, t = G->t, v, w; int lbl[maxV], d; link p; for (v = 0; v < G->V; v++) lbl[v] = -1; QUEUEinit(G->V); lbl[s] = 0; QUEUEput(s); while (!QUEUEempty()) { v = QUEUEget(); for (p = G->adj[v]; p != NULL; p = p->next) { w = p->w; if (RC(p) > 0 && lbl[w] == -1) { lbl[w] = 0; parent[w] = p; QUEUEput(w); } } } if (lbl[t] == -1) return 0; d = M; for (w = t; w != s; w = p->dup->w) { p = parent[w]; if (d > RC(p)) d = RC(p); } return d; }
As últimas linhas do código calculam a capacidade residual do caminho (dirigido) armazenado em parent. A constante M é maior que a capacidade de qualquer arco.
Considere a rede capacitada (não expandida) descrita abaixo. (Este exemplo é uma reprodução aproximada da figura 22.18, p.380, de Sedgewick.)
arco cap s=0 t=13
0-1 10
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-11 3
6-7 5
7-13 9
8-9 3
8-10 5
9-13 6
10-13 9
11-13 6
12-7 7
12-10 7
Suponha que as listas de adjacência são construídas inserindo os arcos na rede, um a um, na ordem dada acima. Agora, a função MaxFlow produz a seguinte sequência de caminhos de aumento (arcos artificiais indicados em vermelho). Cada caminho de aumento tem número mínimo de arcos na correspondente rede de fluxo expandida. O número de arcos e a capacidade residual de cada caminho estão registrados na segunda e terceira colunas respectivamente.
caminho de aumento comprimento cap resid
0-4-11-13 3 3
0-3-10-13 3 3
0-2-9-13 3 3
0-1-7-13 3 3
0-4-6-7-13 4 3
0-3-8-10-13 4 3
0-2-8-10-13 4 2
0-2-8-9-13 4 1
0-1-6-7-13 4 2
0-1-6-11-13 4 1
0-3-5-12-10-13 5 1
0-3-5-12-7-13 5 1
0-3-5-12-10-8-9-13 7 1
0-1-5-12-10-8-9-13 7 1
0-1-5-12-7-6-11-13 7 2
Esses caminhos de aumento produzem a seguinte sequência de fluxos (com "-" representando 0):
0-4-11-13
| 0-3-10-13
| | 0-2-9-13
| | | 0-1-7-13
| | | | 0-4-6-7-13
| | | | | 0-3-8-10-13
| | | | | | 0-2-8-10-13
| | | | | | | 0-2-8-9-13
| | | | | | | | 0-1-6-7-13
| | | | | | | | | 0-1-6-11-13
| | | | | | | | | | 0-3-5-12-10-13
| | | | | | | | | | | 0-3-5-12-7-13
| | | | | | | | | | | | 0-3-5-12-10-8-9-13
| | | | | | | | | | | | | 0-1-5-12-10-8-9-13
| | | | | | | | | | | | | | 0-1-5-12-7-6-11-13
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
arco f f f f f f f f f f f f f f f f
0-1 - - - - 3 3 3 3 3 5 6 6 6 6 7 9
0-2 - - - 3 3 3 3 5 6 6 6 6 6 6 6 6
0-3 - - 3 3 3 3 6 6 6 6 6 7 8 9 9 9
0-4 - 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6
1-5 - - - - - - - - - - - - - - 1 3
1-6 - - - - - - - - - 2 3 3 3 3 3 3
1-7 - - - - 3 3 3 3 3 3 3 3 3 3 3 3
2-3 - - - - - - - - - - - - - - - -
2-8 - - - - - - - 2 3 3 3 3 3 3 3 3
2-9 - - - 3 3 3 3 3 3 3 3 3 3 3 3 3
3-5 - - - - - - - - - - - 1 2 3 3 3
3-8 - - - - - - 3 3 3 3 3 3 3 3 3 3
3-10 - - 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4-1 - - - - - - - - - - - - - - - -
4-6 - - - - - 3 3 3 3 3 3 3 3 3 3 3
4-11 - 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
5-12 - - - - - - - - - - - 1 2 3 4 6
6-11 - - - - - - - - - - 1 1 1 1 1 3
6-7 - - - - - 3 3 3 3 5 5 5 5 5 5 3
7-13 - - - - 3 6 6 6 6 8 8 8 9 9 9 9
8-9 - - - - - - - - 1 1 1 1 1 2 3 3
8-10 - - - - - - 3 5 5 5 5 5 5 4 3 3
9-13 - - - 3 3 3 3 3 4 4 4 4 4 5 6 6
10-13 - - 3 3 3 3 6 8 8 8 8 9 9 9 9 9
11-13 - 3 3 3 3 3 3 3 3 3 4 4 4 4 4 6
12-7 - - - - - - - - - - - - 1 1 1 3
12-10 - - - - - - - - - - - 1 1 2 3 3
O fluxo final é máximo. Ele tem intensidade 30. Eis um corte mínimo (capacidade 30):
0 1 3 5
0-1 3
1-2 3
2-4 3
0-3 2
3-4 1
3-5 2
5-6 2
6-7 2
4-7 3
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.7, p.384, Sedgewick): O número de caminhos de aumento usados pela combinação de MaxFlow com ShrtstAugmPath nunca é maior que VA/2, sendo V o número de vértices e A o número de arcos originais.
A prova da propriedade depende do conceito de arco crítico. Um arco de um caminho de aumento é crítico se tiver capacidade residual mínima no caminho. Depois da operação de aumento de fluxo ao longo do caminho de aumento, a capacidade de um arco crítico é reduzida a zero e portanto o arco não poderá ser usado pelo caminho de aumento seguinte (mas poderá vir a ser usado por caminhos de aumento subsequentes se sua capacidade residual aumentar nesse meio tempo).
A prova da propriedade depende de dois fatos:
Esses dois fatos não são óbvios; sua prova exige algum esforço e será omitida.
Como todo caminho de aumento tem comprimento menor que V, cada arco do digrafo pode ser crítico em não mais que V/2 caminhos de aumento. Portanto, o número total de caminhos de aumento é menor que VA/2, como queríamos provar.