Problema da vazão máxima

O problema do fluxo máximo consiste em encontrar fluxo através de uma rede de fluxo que seja máximo O problema do fluxo máximo pode ser visto como um caso especial de um problema de fluxo mais complexo. Ele é o problema fluxo de mutiplas-mercadorias com so uma so mercadoria, e também como o problema de fluxo de custo-minimo com todos os fluxos zerados. O fluxo máximo esta relacionado ao corte em uma rede pelo Teorema do mínimo corte-máximo fluxo.

Soluções

Dado um grafo $G(V,E)$, onde cada aresta $u,v$ tem uma capacidade $c(u,v)$, nos queremos determinar o fluxo máximo $f$, sujeito a certas limitações. Existem varias maneiras para solucionar este problema:

Método	Complexidade	Descrição
Força bruta	$O(2^{V-2}E)$	Encontra os menor de todos os cortes que separa $s$ e $t$.
Programação linear		Restrições dadas pelas definições de uma fluxo legal. Otimizar $\sum _{v\in V}f(s,v)$.
Algoritmo de Ford-Fulkerson	$O(E\cdot maxflow)$	Tão logo seja aberto um caminho através da rede, envie o maior fluxo possível através dele.
Algoritmo de Edmonds-Karp	$O(VE^{2})$	Uma especialização do algoritmo de Ford-Fulkerson, busca caminhos com busca em largura.
Algoritmo de remarcagem-para-frente	$O(V^{3})$	Rearranja os nodos em vários pesos tal que o um acréscimo máximo de fluxo corra de $s$ para $t$ "por si proprio".

Referência

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 26: Maximum Flow, pp. 643–700.