Fluxos em Redes
Definição do problema Seja $G$ um grafo orientado com capacidades não-negativas $w_{i, j}$ nos arcos, e dois vértices $s$ (origem) e $t$ (destino). Qual o fluxo máximo que pode ser enviado de $s$ para $t$ respeitando as capacidades dos arcos? A tabela abaixo mostra 3 algoritmos famosos que resolvem o problema do fluxo máximo em redes. Algoritmo Complexidade de tempo Complexidade de espaço Observações Ford-Fulkerson $\mathcal{O}(n)$ $\mathcal{O}(n)$ Edmonds-Karp $\mathcal{O}(n)$ $\mathcal{O}(n)$ Dinic $\mathcal{O}(n)$ $\mathcal{O}(n)$ Algoritmo de Ford-Fulkerson Este algoritmo busca por um caminho aumentante $p$ a cada iteração, ou seja, um caminho de $s$ para $t$ que passa somente por arcos com capacidade positiva no grafo residual. O grafo residual é inicializado igual ao grafo original, mas assim que um fluxo escoa por um caminho, as capacidades residuais dos arcos pertencentes ao caminho são atualizadas. ...