Algoritmo Ford-Fulkerson

Neste tutorial, você aprenderá o que é o algoritmo Ford-Fulkerson. Além disso, você encontrará exemplos de trabalho para encontrar o fluxo máximo em uma rede de fluxo em C, C ++, Java e Python.

O algoritmo Ford-Fulkerson é uma abordagem gananciosa para calcular o fluxo máximo possível em uma rede ou gráfico.

Um termo, rede de fluxo , é usado para descrever uma rede de vértices e arestas com uma fonte (S) e um sorvedouro (T). Cada vértice, exceto S e T , pode receber e enviar uma quantidade igual de coisas através dele. S pode apenas enviar e T pode apenas receber coisas.

Podemos visualizar a compreensão do algoritmo utilizando um fluxo de líquido dentro de uma rede de tubos de diferentes capacidades. Cada tubo tem uma certa capacidade de líquido que pode transferir em uma instância. Para este algoritmo, vamos descobrir quanto líquido pode fluir da fonte para o coletor em uma instância usando a rede.

Gráfico de rede de fluxo

Terminologias Usadas

Caminho Aumentando

É o caminho disponível em uma rede de fluxo.

Gráfico Residual

Ele representa a rede de fluxo que possui fluxo adicional possível.

Capacidade Residual

É a capacidade da borda após subtrair o fluxo da capacidade máxima.

Como funciona o algoritmo Ford-Fulkerson?

O algoritmo segue:

  1. Inicialize o fluxo em todas as bordas para 0.
  2. Embora haja um caminho de aumento entre a origem e o coletor, adicione esse caminho ao fluxo.
  3. Atualize o gráfico residual.

Também podemos considerar o caminho reverso, se necessário, porque se não os considerarmos, podemos nunca encontrar um fluxo máximo.

Os conceitos acima podem ser entendidos com o exemplo abaixo.

Exemplo Ford-Fulkerson

O fluxo de todas as arestas é 0 no início.

Exemplo de gráfico de rede de fluxo
  1. Selecione qualquer caminho arbitrário de S a T. Nesta etapa, selecionamos o caminho SABT. Encontre um caminho
    A capacidade mínima entre as três arestas é 2 (BT). Com base nisso, atualize o fluxo / capacidade para cada caminho. Atualize as capacidades
  2. Selecione outro caminho SDCT. A capacidade mínima entre essas bordas é 3 (SD). Encontre o próximo caminho
    Atualize as capacidades de acordo com isso. Atualize as capacidades
  3. Agora, consideremos também o BD de caminho reverso. Selecionando o caminho SABDCT. A capacidade residual mínima entre as bordas é 1 (DC). Encontre o próximo caminho
    Atualizando as capacidades. Atualizar as capacidades
    A capacidade para os caminhos direto e reverso são considerados separadamente.
  4. Somando todos os fluxos = 2 + 3 + 1 = 6, que é o fluxo máximo possível na rede de fluxo.

Observe que, se a capacidade de qualquer borda estiver cheia, esse caminho não poderá ser usado.

Exemplos de Python, Java e C / C ++

Python Java C C ++ 
 # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = (False) * (self.ROW) queue = () queue.append(s) visited(s) = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph(u)): if visited(ind) == False and val> 0: queue.append(ind) visited(ind) = True parent(ind) = u return True if visited(t) else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = (-1) * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph(parent(s))(s)) s = parent(s) # Adding the path flows max_flow += path_flow # Updating the residual values of edges v = sink while(v != source): u = parent(v) self.graph(u)(v) -= path_flow self.graph(v)(u) += path_flow v = parent(v) return max_flow graph = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)) g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))
 // Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson ( static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph()(), int s, int t, int p()) ( boolean visited() = new boolean(V); for (int i = 0; i < V; ++i) visited(i) = false; LinkedList queue = new LinkedList(); queue.add(s); visited(s) = true; p(s) = -1; while (queue.size() != 0) ( int u = queue.poll(); for (int v = 0; v 0) ( queue.add(v); p(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph()(), int s, int t) ( int u, v; int Graph()() = new int(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph(u)(v) = graph(u)(v); int p() = new int(V); int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) ( int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p(v)) ( u = p(v); path_flow = Math.min(path_flow, Graph(u)(v)); ) for (v = t; v != s; v = p(v)) ( u = p(v); Graph(u)(v) -= path_flow; Graph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) public static void main(String() args) throws java.lang.Exception ( int graph()() = new int()() ( ( 0, 8, 0, 0, 3, 0 ), ( 0, 0, 9, 0, 0, 0 ), ( 0, 0, 0, 0, 7, 2 ), ( 0, 0, 0, 0, 0, 5 ), ( 0, 0, 7, 4, 0, 0 ), ( 0, 0, 0, 0, 0, 0 ) ); FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); ) )
 / Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity(MAX_NODES)(MAX_NODES); int flow(MAX_NODES)(MAX_NODES); int color(MAX_NODES); int pred(MAX_NODES); int min(int x, int y) ( return x < y ? x : y; ) int head, tail; int q(MAX_NODES + 2); void enqueue(int x) ( q(tail) = x; tail++; color(x) = B; ) int dequeue() ( int x = q(head); head++; color(x) = C; return x; ) // Using BFS as a searching algorithm int bfs(int start, int target) ( int u, v; for (u = 0; u < n; u++) ( color(u) = A; ) head = tail = 0; enqueue(start); pred(start) = -1; while (head != tail) ( u = dequeue(); for (v = 0; v 0) ( enqueue(v); pred(v) = u; ) ) ) return color(target) == C; ) // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) ( int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) ( for (j = 0; j = 0; u = pred(u)) ( increment = min(increment, capacity(pred(u))(u) - flow(pred(u))(u)); ) for (u = n - 1; pred(u)>= 0; u = pred(u)) ( flow(pred(u))(u) += increment; flow(u)(pred(u)) -= increment; ) // Adding the path flows max_flow += increment; ) return max_flow; ) int main() ( for (int i = 0; i < n; i++) ( for (int j = 0; j < n; j++) ( capacity(i)(j) = 0; ) ) n = 6; e = 7; capacity(0)(1) = 8; capacity(0)(4) = 3; capacity(1)(2) = 9; capacity(2)(4) = 7; capacity(2)(5) = 2; capacity(3)(5) = 5; capacity(4)(2) = 7; capacity(4)(3) = 4; int s = 0, t = 5; printf("Max Flow: %d", fordFulkerson(s, t)); )
 // Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph(V)(V), int s, int t, int parent()) ( bool visited(V); memset(visited, 0, sizeof(visited)); queue q; q.push(s); visited(s) = true; parent(s) = -1; while (!q.empty()) ( int u = q.front(); q.pop(); for (int v = 0; v 0) ( q.push(v); parent(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph(V)(V), int s, int t) ( int u, v; int rGraph(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph(u)(v) = graph(u)(v); int parent(V); int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) ( int path_flow = INT_MAX; for (v = t; v != s; v = parent(v)) ( u = parent(v); path_flow = min(path_flow, rGraph(u)(v)); ) for (v = t; v != s; v = parent(v)) ( u = parent(v); rGraph(u)(v) -= path_flow; rGraph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) int main() ( int graph(V)(V) = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)); cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; )

Aplicativos Ford-Fulkerson

  • Tubulação de distribuição de água
  • Problema de correspondência bipartida
  • Circulação com demandas

Artigos interessantes...