Problema do fluxo máximo

Imagine que uma empresa deseja transportar a maior quantidade possível de produtos de uma cidade para outra, através da rede rodoviária. A restrição do transporte é que cada estrada da rede suporta um número finito de caminhões. Este é um exemplo de instância do problema do fluxo máximo, que tem aplicações em inúmeras áreas. Outro problema, por exemplo, que pode ser modelado da mesma maneira é maximizar a quantidade de dados enviada de um roteador a outro na Internet, sob a restrição de que cada cabo suporta uma quantidade finita de transmissão.

O primeiro algoritmo proposto para resolver o problema do fluxo máximo foi o célebre método dos caminhos de aumento de Ford e Fulkerson [11]. O método genérico é pseudo-polinomial, mas existem implementações que tornam a complexidade polinomial. Alguns exemplos são o algoritmo dos caminhos de aumento de comprimento mínimo, proposto por Edmonds e Karp [9], o algoritmo dos fluxos bloqueadores de aumento, idealizado por Dinits [8], o algoritmos dos caminhos de maior aumento, também proposto por Edmonds e Karp [9], e o algoritmo capacity scaling de Ahuja e Orlin [3].

Algum tempo depois, Goldberg e Tarjan [13] propuseram um novo método para resolver o problema do fluxo máximo, conhecido como método do pré-fluxo. Eles mesmos sugeriram uma implementação para o método conhecida como algoritmo dos vértices ativos de maior rótulo. Outras implementações são o algoritmo da fila de vértices ativos, adaptado por Goldberg de uma idéia de Shiloach e Vishkin [19], e o algoritmo excess scaling, idealizado por Ahuja e Orlin [2].