O que é o problema do fluxo máximo?

Pergunta pelo maior fluxo total que pode ser roteado de um nó de origem designado a um nó de destino designado através de uma rede de arestas direcionadas, cada uma limitada por uma capacidade.

Como funciona o algoritmo de Edmonds-Karp?

Usa repetidamente busca em largura para encontrar o caminho de aumento disponível mais curto da origem ao destino no grafo residual, empurra o máximo fluxo possível ao longo desse caminho (limitado por sua menor capacidade restante) e repete até que nenhum caminho reste.

O que é um grafo residual?

É um grafo que rastreia quanto fluxo adicional ainda pode ser empurrado ao longo de cada aresta (capacidade restante) mais uma aresta 'reversa' para o fluxo já enviado, o que permite ao algoritmo efetivamente 'desfazer' uma escolha subótima anterior.

O que é o teorema do fluxo máximo-corte mínimo?

Estabelece que o fluxo máximo da origem ao destino sempre é exatamente igual à capacidade total mínima de qualquer 'corte' (conjunto de arestas que, se removidas, desconectariam a origem do destino) — uma garantia fundamental de por que Edmonds-Karp encontra o verdadeiro ótimo.

Por que usar BFS em vez de qualquer caminho (Ford-Fulkerson)?

O Ford-Fulkerson simples pode escolher caminhos de aumento arbitrariamente ruins e rodar lentamente em certos grafos; sempre escolher o caminho mais curto via BFS (Edmonds-Karp) garante que o algoritmo termine em tempo polinomial, O(VE²).

O que significa a seta '->' na entrada de arestas?

Indica uma aresta direcionada — A->B:10 significa que até 10 unidades de fluxo podem se mover de A para B, mas não de B para A (a menos que uma aresta separada B->A também seja inserida).

Quantos nós esta calculadora pode processar?

Esta calculadora suporta até 30 nós, mantendo o cálculo de Edmonds-Karp instantâneo enquanto cobre a grande maioria dos exemplos de rede inseridos manualmente.

Onde o fluxo máximo é usado na vida real?

Modela a alocação de largura de banda de rede, roteamento de tráfego e transporte, correspondência bipartida (atribuição de empregos, apps de namoro), distribuição de tubulações de água/petróleo e segmentação de imagens em visão computacional.

Calculadora de Fluxo de Rede — Encontre o Fluxo Máximo Através de uma Rede

Nossa Calculadora de Fluxo de Rede encontra a quantidade máxima de fluxo que pode ser enviada de um nó de origem a um nó de destino através de um grafo direcionado onde cada aresta tem uma capacidade limitada, usando o algoritmo de Edmonds-Karp (Ford-Fulkerson baseado em BFS), a partir da sua rede inserida como uma lista de arestas de texto simples (ex. A->B:10, B->C:5).

Resposta rápida

Insira seu grafo direcionado com capacidades e um par origem/destino para encontrar instantaneamente o fluxo máximo via o algoritmo de Edmonds-Karp.

Arestas direcionadas (separadas por vírgula)

Digite arestas como NóA->NóB:capacidade, ex. A->B:10, B->C:5.

Origem

Destino

Como usar Calculadora de Fluxo de Rede — Fluxo Máximo via Edmonds-Karp Online

1
Insira seu grafo direcionado com capacidades como uma lista de arestas separadas por vírgulas, ex. A->B:10, B->C:5.
2
Insira os nomes dos nós de origem e destino.
3
Clique em 'Calcular' para encontrar o fluxo máximo via Edmonds-Karp.

Por que usar Calculadora de Fluxo de Rede — Fluxo Máximo via Edmonds-Karp Online?

O fluxo máximo pergunta quanto total de 'coisa' (dados, água, tráfego) pode se mover de uma origem a um destino através de uma rede onde cada aresta tem capacidade limitada. O algoritmo de Edmonds-Karp resolve isso exatamente: encontra repetidamente qualquer caminho de aumento mais curto da origem ao destino usando BFS no grafo residual (o grafo de capacidade restante, incluindo arestas de 'desfazer' para o fluxo já enviado), empurra o máximo fluxo possível ao longo desse caminho e repete até que nenhum caminho de aumento reste — momento em que o fluxo total empurrado é igual ao fluxo máximo possível, um fato garantido pelo teorema do fluxo máximo-corte mínimo.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Caminho Mais Curto de Dijkstra — Grafos Ponderados Online

Encontre o caminho mais curto e a distância total entre dois nós em um grafo ponderado usando o algoritmo de Dijkstra. Calculadora gratuita com uma entrada simples de lista de arestas.

Calculadora de Árvore Geradora Mínima — Algoritmo de Kruskal Online

Encontre a árvore geradora mínima de um grafo ponderado usando o algoritmo de Kruskal. Calculadora gratuita com uma entrada simples de lista de arestas e detecção de ciclos via union-find.

Solucionador de Programação Linear — Método de Ponto de Vértice de 2 Variáveis Online

Resolva um programa linear de 2 variáveis encontrando e avaliando cada ponto de vértice da região factível. Calculadora gratuita, maximize ou minimize com restrições lineares.