Flujo máximo y corte mínimo

Introduce aristas dirigidas entre S, A, B, C, D y T como S -> A 10; S es la fuente y T el sumidero. Se aceptan coma y punto decimal, con hasta seis decimales. Las capacidades pueden ser cero; cada par dirigido admite un total de 1000000 como máximo. Se ignoran líneas vacías y se suman líneas paralelas. Un sumidero inaccesible da flujo máximo cero. Las entradas, incluso redes incompletas o no válidas, y la espera de animación se guardan localmente. Recargar espera una acción; no se guarda el progreso del cálculo. El grafo usa hasta tres cifras significativas; ≈ indica redondeo. La descripción de la arista y sus detalles ofrecen toda la precisión mostrada. Ocultar la página pausa la animación hasta reanudarla explícitamente.

Calcular obtiene inmediatamente el flujo máximo final. Paso continúa por un camino aumentante más corto; Animar continúa el mismo cálculo y Pausa lo detiene. Reiniciar borra el flujo para la entrada actual. Editar detiene la animación y elimina resultados antiguos. El ejemplo Arista inversa muestra cómo un camino residual puede deshacer una elección anterior.

Las aristas indican flujo/capacidad. El naranja señala el último camino residual; una arista discontinua se recorre al revés. Al terminar, las aristas rojas cruzan el corte mínimo y los contornos azules identifican el lado S. La partición muestra el lado S antes de la barra y el lado T después. La capacidad del corte iguala el flujo máximo. Los detalles ofrecen valores accesibles en ambas direcciones residuales. Con aristas originales opuestas, la capacidad residual combina capacidad directa disponible y flujo opuesto cancelable; los flujos mostrados usan una representación válida tras cancelar flujos opuestos.

Edmonds–Karp utiliza búsqueda en anchura en el grafo residual. El dibujo tiene seis nodos fijos; en redes densas pueden cruzarse etiquetas, para eso está la tabla. Los decimales usan coma flotante de JavaScript y pueden redondearse en las últimas cifras. Princeton: flujo máximo.