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 ${\displaystyle G(V,E)}$, onde cada aresta ${\displaystyle u,v}$ tem uma capacidade ${\displaystyle c(u,v)}$, nos queremos determinar o fluxo máximo ${\displaystyle f}$, sujeito a certas limitações. Existem varias maneiras para solucionar este problema:

Método	Complexidade	Descrição
Força bruta	${\displaystyle O(2^{V-2}E)}$	Encontra os menor de todos os cortes que separa ${\displaystyle s}$ e ${\displaystyle t}$.
Programação linear		Restrições dadas pelas definições de uma fluxo legal. Otimizar ${\displaystyle \sum _{v\in V}f(s,v)}$.
Algoritmo de Ford-Fulkerson	${\displaystyle 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	${\displaystyle O(VE^{2})}$	Uma especialização do algoritmo de Ford-Fulkerson, busca caminhos com busca em largura.
Algoritmo de remarcagem-para-frente	${\displaystyle O(V^{3})}$	Rearranja os nodos em vários pesos tal que o um acréscimo máximo de fluxo corra de ${\displaystyle s}$ para ${\displaystyle 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.