ALGORITMO FORD FULKERSON
PRESENTADO POR:
ALVARO LUIS RIOS GARZON 2181705
HORACIO ANTONIO CAMACHO HOLGUIN 2180986
JUAN PABLO CLARO PEREZ 2181707
PROFESOR:
HECTOR NIÑO QUIÑONEZ
UNIVERSIDAD INDUSTRIAL DE SANTANDER
INGENIERIA DE SISTEMAS
BUCARAMANGA SANTANDER
2019
FORD FULKERSON
El algoritmo de Ford Fulkerson, consiste en buscar los caminos en los que se pueda
aumentar el flujo hasta hallar el flujo máximo en una red de flujo. Su nombre viene
en honor a los apellidos de sus dos creadores: L. R. Ford. y D. R. Fulkerson en el
año de 1956.
Se entiende por red de flujo máximo (Flow Network) a un dígrafo G= (V, E) en el
cual cada arista (𝑢, 𝑣) ∈ 𝐸 tiene una capacidad no negativa donde 𝑐(𝑢, 𝑣) ≥ 0,
además, si la red tiene la arista (𝑢, 𝑣), no puede tener la arista (𝑣, 𝑢).
Sea G= (V, E) una red de flujo con una función de capacidad C, una fuente y un
sumidero t, un flujo en G es una función real 𝑓: 𝑉𝑋𝑉 → 𝑅 que satisface:
Restricción de capacidad ∀𝑢, 𝑣 ∈ 𝑉 es necesario que 0 < 𝑓(𝑢, 𝑣) ≤ 𝐶(𝑢, 𝑣)
Conservación del flujo: ∀𝑢 ∈ 𝑉 − {𝑆, 𝑡} es necesario que Σ𝑓(𝑣, 𝑢) = Σ𝑓(𝑢, 𝑣) cuando
(𝑢, 𝑣) ∉ 𝐸 → 𝑓(𝑢. 𝑣) = 0
Por lo tanto, los grafos con los que trabaja el algoritmo de Ford Fulkerson son
dígrafos y a su vez grafos ponderados, puesto que siempre se va a tener una fuente
y un sumidero donde todos sus caminos están entrelazados, no obstante, la materia
prima solo puede ser enviada en un sentido, por lo tanto, es imprescindible la
utilización de dígrafos; a continuación, se puede observar una red de flujo
PROBLEMA DEL FLUJO MAXIMO
Dada una red de flujo G con la fuente S y sumidero t, si se desea determinar el
mayor flujo que puede moverse en una red, se debe utilizar el algoritmo de Ford-
Fulkerson, planteado a continuación
Ford-Fulkerson(G,S,t): se inicializa el flujo f a cero y mientras exista un camino de
aumento (Augmenting Path) P en la red residual, Gf aumentará el flujo f a través de
p, al final se retornara f con el valor del flujo
Imagen 1: Seudocódigo para el algoritmo de Ford-Fulkerson
Tomado de: [Link]
Red residual: Dado un flujo f en una red de flujo G, la red residual Gf se forma con
las aristas y sus capacidades alteradas por el flujo f en G.
.
Imagen 2: Red residual, grafo
Tomado por: Alvaro Luis Rios Garzon
Fecha: 19 de agosto del 2019
Una arista de G puede admitir una cantidad de flujo adicional igual a la capacidad
de la arista, menos al flujo de la arista; si el valor es positivo, la arista hace parte de
G con una capacidad residual de 𝐶𝑓(𝑢, 𝑣) = 𝐶(𝑢, 𝑣) − 𝑓(𝑢, 𝑣)
Puesto que se puede reducir el flujo por una arista. Dado 𝑓(𝑢, 𝑣), la arista 𝑓(𝑢, 𝑣)
representa la cantidad de flujo en la cual se reduce el flujo 𝑓(𝑢, 𝑣)
Supongase una red G con una fuente S y un sumidero t sea un flujo f en G y
considere un par de verices 𝑢, 𝑣 ∈ 𝑉 la capacidad residual se define como:
𝐶(𝑢, 𝑣) − 𝑓(𝑢, 𝑣) 𝑠𝑖 (𝑢, 𝑣) ∈ 𝐸
𝐶𝑓(𝑢, 𝑣): 𝑓(𝑢, 𝑣) si (𝑢, 𝑣) ∈ 𝐸
0 otro caso
Camino de aumento: Dados una red de flujo G= (V, E) y un flujo f, un camino de
aumento, p es un camino desde S hasta t en una red residual Gf.
La capacidad residual: Es la máxima cantidad en la que se puede incrementar el
flujo en cada arista en un camino de aumento p, sin violar la restricción de
capacidad 𝐶𝑓(𝑝) = min{𝐶𝑓(𝑢, 𝑣) | (𝑢, 𝑣) ∈ 𝐸𝑝}
1. El tipo de grafo que utiliza el algoritmo de Ford-Fulkerson son ponderados y
digrafos.
2. El algoritmo utiliza una lista enlazada apollada de una pila, y registros.
3. El ejemplo utilizado fue:
AVYASA Logistics surte gasolina que es enviada a los diferentes tanques de
almacenamiento a través de los oleoductos indicados en la red mostrada, se
requiere determinar el flujo máximo a surtirse a través de los oleoductos hasta
sus terminales de almacenamiento y reparto, debido a que se espera un
incremento en la demanda de este producto. Para ello se debe realizar el
análisis para conocer cuál es el flujo máximo de abastecimiento, la distribución
se presenta acorde al siguiente diagrama:
Imagen 3: Ejemplo de flujo máximo
Tomado de: Análisis de redes de distribución logística con el algoritmo de Ford-Fulkerson por
Vazquez Martin
4. El código en c++ es el siguiente:
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Número de vertices en el grafo
#define V 5
/* Devuelve verdadero si hay una ruta desde la fuente 's' hasta el sumidero 't' en
gráfico residual También llena parent[] para almacenar la ruta */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
//Crea un vector de vistados y marca todos los vertices como no visitados
bool visited[V];
memset(visited, 0, sizeof(visited));
//Crea una cola, encola el vertice fuente y marca el mismo como visitado
queue <int> q;
[Link](s);
visited[s] = true;
parent[s] = -1;
//Ejecuta un bucle BFS estándar
while (![Link]())
{
int u = [Link]();
[Link]();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
[Link](v);
parent[v] = u;
visited[v] = true;
}
}
}
// Si el BFS llega hasta el sumidero a partir de la fuente, entonces se regresa true, en
// el caso contrario se devuelve false
return (visited[t] == true);
}
//Devuelve el flujo máximo desde la fuente al sumidero en el grafo dado
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
// Se crea un grafo residual, el cual se llena con las capacidades del grafo original
//como capacidades residuales en el grafo residual
int rGraph[V][V];
// Grafo residual donde rGraph[i][j] indica la capacidad residual de las aristas
// desde i a j (hay una arista si rGraph[i][j] es 0, en el caso contrario no hay)
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // Este arreglo es llenado por el BFS y almacenado por el camino
int max_flow = 0; // Inicialmente el flujo máximo es 0
// Se aumenta el flujo mientras halla caminos desde la fuente hasta el sumidero
while (bfs(rGraph, s, t, parent))
{
// Encuentra la capacidad residual mínima de las aristas a lo largo del camino
// llenado por el BFS. Es decir, encuentra el flujo máximo a través del camino
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// actualiza la capacidad residual de las aristas y aristas reversas a lo largo
// del camino
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Agrega una ruta de flujo al flujo general
max_flow += path_flow;
}
// Devuelve el flujo general
return max_flow;
}
int main()
{
int graph[V][V] = { {0, 8, 0, 4, 7},
{0, 0, 5, 0, 5},
{0, 0, 0, 0, 6},
{0, 0, 5, 0, 2},
{0, 0, 0, 0, 0}
};
cout << "El flujo máximo posible es: " << fordFulkerson(graph, 0, 4);
return 0;
}
5. El orden de complejidad está dado por:
Imagen 4: Orden de complejidad Ford-Fulkerson
Tomado por: Juan Pablo Claro Perez
Fecha: 19 de agosto del 2019.
6. Aplicaciones del algoritmo de Ford Fulkerson, Una de las mayores
aplicaciones del algoritmo es para determinar la cantidad máxima de
material o liquido que se puede enviar a través de conductos desde un punto
de partida hasta un punto de llegada de tal manera que no se rompan los
conductos y que no se tengan perdidas por no poder tomar todo el material
posible, como lo puede ser a la hora de extraer el petróleo, bombeo de agua
de una ciudad, entre otras.
