Acelerando Ford-Fulkerson
Ejemplo: Sea $G$ un grafo
- Podemos resolver el problema del flujo máximo.
- Veamos que el flujo máximo es de 1000 (Se puede resolver con 2 caminos de aumento)
La selección de caminos $s-t$ que sean malos pueden relentizar mucho la finalización del algoritmo.
Selección eficiente de camino $s-t$
Intentar elegir aquellos caminos con mayor cuellos de botella.
- Idealmente, seleccionar de mayor cuello de botella para cada paso.
- Mantener esta información actualizada puede ser costoso.
$\implies$ Existen varios métodos para intentar realizar selecciones convenientes.
Método de Parámetro de escalado ∆
Se utilizará un parámetro ∆
Y sólo se buscará aquellos $P$ caminos $s-t$ con $bottleneck(P,f)>∆$
Inicialmente ∆ tomará la potencia de 2 más grande que sea no mayor a la suma de la capacidad de los ejes que salen de $s$.
$\implies$Repetir hasta hallar el flujo máximo.
- Armar grafo residual únicamente con los ejes que superen ∆.
- Buscar caminos $s-t$ en ese subgrafo y proceder igual que en $Ford-Fulkerson$.
- De no existir más caminos, se reduce ∆ a la mitad
Pseudocódigo