El algoritmo maxflow calcula el flujo en estado estacionario , no el volumen de fluido.
Si comprende la afirmación anterior, también podrá comprender la intuición.
Considere las capacidades de red dadas.
- ¿Cuáles son los mejores algoritmos de partición de gráficos para gráficos grandes?
- ¿Por qué alguien no puede encontrar un algoritmo para la detección de imágenes que funcione mejor que SIFT (Scale Invariant Feature Transform)? ¿De dónde viene exactamente el problema?
- Cómo alterar el rango de un bucle for dentro del bucle en Python
- ¿Qué aplicación utiliza el algoritmo?
- ¿Cuál es la mejor manera de comprender y dominar la estructura de datos?
Podemos ver que hay 4 caminos en aumento
- E-> C-> A-> S
- E-> C-> D-> B-> S
- F-> D-> C-> A-> S
- F-> D-> B-> S
Elija la ruta 2, es decir: E-> C-> D-> B-> S
Claramente, esto agrega 10 unidades al flujo estable (bordes verdes), pero no es lo mejor, ya que ahora no nos quedan rutas de aumento debido al cuello de botella en C-> D, pero podríamos haber tenido Un flujo estable de 20 unidades.
Aquí surge la idea de maximizar el flujo estable, sin tener en cuenta el volumen de fluido en la red. Después de insertar 10 unidades de fluido verde en la ruta E-> C-> D-> B-> S, podemos comenzar a insertar fluido rojo en el borde F-> D 1 unidad a la vez, hasta 10 unidades. Los fluidos verde y rojo no se mezclan entre sí. Veamos cómo se ve la red después de inyectar 1 unidad de líquido rojo en F-> D.
Tenga en cuenta que los números en los bordes denotan la presión ejercida en ese borde por los fluidos. por ejemplo: c-> d tiene 10 unidades de presión ya que el nodo C recibe 10 unidades de fluido.
Después de inyectar 10 unidades de fluido, tendremos la siguiente red:
Y esa es la intuición detrás de los bordes inversos. En palabras simples, empuja el líquido hacia atrás, forzándolo en un camino diferente y dejando algo de líquido estancado en la red mientras lo hace.
