¡Hola, Habr! Al resolver el problema del flujo máximo, me encontré con el hecho de que en todas las fuentes que conozco se daba una descripción formal de los propios algoritmos, lo que dificultaba mucho la comprensión del material presentado. Y en este artículo intentaré desmontar el algoritmo Ford-Fulkerson a un nivel básico con un ejemplo específico, para que después de leer este artículo, al menos entiendas la esencia básica del algoritmo en sí.
Formulación del problema
Tenemos el siguiente gráfico dirigido , en el que el peso del borde denota la capacidad entre vértices. Es necesario encontrar el caudal máximo que se puede pasar de la fuente
al drenaje
.
¿Cómo funciona el algoritmo en sí?
La red residual debe entenderse como la misma gráfica que está en la entrada, pero en este caso realizaremos algunas operaciones sobre ella:
Envía una cierta cantidad de flujo desde el vértice actual a los vecinos.
Devuelve una cierta cantidad de flujo de los vértices vecinos al actual.
En el momento inicial en el tiempo, el flujo que queremos que pase a través de nuestra red debe ser igual a cero. La malla residual es la misma que la malla original.
. , , .
, .
, .
( , 0) . , , .
.
, , .
, , .
???
-2 .
, .
:
. , 2 .
, , 
.
, 2- :
3
. , .
:
3- :
1 .
.
:
4- :
4 .
.
:
- , . .
: 10 .
, , !
!