Algoritmo de Ford-Fulkerson

Cuando trabajamos con redes existe un problema habitual: encontrar el flujo máximo. Consiste en maximizar el valor de un flujo $F$ de la red a tratar, para lo cual necesitamos los conceptos de corte y camino de aumento.

El algoritmo de Ford-Fulkerson nos ayuda a resolver este problema, unicamente utilizando la red en cuestión. Mas que un algoritmo es como un metodo goloso, ya que nos deja muchas libertades a la hora de cumplir ciertos pasos. Como tal, la idea es la siguiente:

Encontrar un camino de $s$ a $t$ por el que pueda correr flujo, es decir, un camino de aumento
Llenar de flujo lo mas que podamos dicho camino
Armar la red residual de la red que nos quedo con el flujo factible
Buscar un nuevo camino de aumento, y repetir
Si no hay camino de aumento, quiere decir que logramos maximizar $F$

Si lo piensan, llamarlo algoritmo es bastante generoso. Por ejemplo, el paso 1 indica encontrar un camino de $s$ a $t$ , pero no nos indica como. Podriamos usar DFS o BFS, o buscar el camino mas corto bajo ciertos criterios con algoritmos como el de Dijkstra o el de Bellman-Ford (si, el mismo Ford que aca). Lo loco es que como tal, no cambia la complejidad final. A su vez, en el paso 3 de construir la red residual, no se nos indica como, por lo que ahi habria que tener ingenio propio.

El pseudocodigo del algoritmo podria escribirse como sigue:

FordFulkerson(N):
  definir un flujo inicial en N // Por ejemplo, f(e) = 0 para todo e
  while (exista P camino de aumento en R(N, f)) do:
	for (cada arco (v -> w) de P) do:
	  if ((v -> w) pertenece a X) do:
		f((v -> w)) = f((v -> w)) + dist(P)
	  else:
	    f((w -> v)) = f((w -> v)) - dist(P)
	  end if;
    end for;
  end while;

A su vez, la complejidad final del algoritmo, si construimos la red residual de manera lineal (es decir, en $O (m)$ ) y utilizaramos BFS (con complejidad $O (n + m)$ , obtendriamos una complejidad final de $O (F n + F m)$ , donde $F$ es el flujo. Esto puede reducirse a $O (F m)$ , ya que en las redes habituales (es decir, las que son conexas y no forman un caso trivial como una lista enlazada) podemos afirmar que $n < m$ , por lo que $m$ es de orden mayor.

La logica del calculo de esta complejidad radica en que, en el peor de los casos, cada vez que calculamos el flujo de un posible camino, aumentamos a $F$ en uno. Si esto sucede todas las iteraciones, habriamos hecho $F$ ejecuciones del algoritmo, quedandonos asi la complejidad antes mencionada de $O (F m)$ .