Algoritmo De Ford Y Fulkerson
Páginas: 3 (709 palabras)
Publicado: 26 de noviembre de 2012
Algoritmo de Ford y Fulkerson (1962) para determinar el flujo máximo en una red (método de las etiquetas).
Asignar un índice (numerar) a los nodos de tal manera que la fuente tenga el 1 y eldestino la n.
El arco que une el nodo i con el j tiene capacidad cij. En caso de que no pueda haber flujo entre i y j, entonces cij = 0.
Para cada arco se define la capacidad disponible o remanente(excess capacity):
Se inicia con todos los flujos xij ajustados al valor cero. A continuación se marca cada arco con sus capacidades disponibles dij y dji.
PASO 1
Comenzando en la fuente, seidentifica el conjunto N1 de todos los nodos que están conectados con ella mediante un arco con capacidad disponible positiva. Se asigna la denominación k para los nodos en N1. Etiquete cada nodo k enN1 mediante el par ordenado (ek , pk) donde:
ek = d1k = Capacidad disponible del arco que une la fuente con el nodo k
pk = Nodo antecedente al nodo k
En este paso pk = 1, puesto que se estáavanzando desde la fuente (nodo 1).
A partir de este momento se asume que el nodo fuente está etiquetado.
Si en este paso se ha etiquetado el nodo n (destino), se procede directamente al paso 5.PASO 2
Elegir el nodo en N1 con el menor índice (número); forme el conjunto N2 con aquellos nodos no etiquetados que están unidos al nodo k mediante un arco con capacidad remanente positiva. Sino hay nodos sin etiquetar, se continúa con el siguiente nodo en N1 con el menor índice. Utilice la denominación m para cada nodo en N2. Asigne una etiqueta a cada nodo no etiquetado en N2 medianteel par ordenado (em , pm) donde:
em = min { dkm , ek }
pm = k
Observe que em es el mínimo de las capacidades disponibles de los arcos desde la fuente al nodo k y desde k al nodo m. Por suparte pm denota al nodo k que antecede al nodo m.
Este procedimiento se repite para cada nodo en N1.
PASO 3
Repita el paso 2 con Nr substituyendo a Nr-1 (r = 3, 4, …, n-1)
Después de un...
Asignar un índice (numerar) a los nodos de tal manera que la fuente tenga el 1 y eldestino la n.
El arco que une el nodo i con el j tiene capacidad cij. En caso de que no pueda haber flujo entre i y j, entonces cij = 0.
Para cada arco se define la capacidad disponible o remanente(excess capacity):
Se inicia con todos los flujos xij ajustados al valor cero. A continuación se marca cada arco con sus capacidades disponibles dij y dji.
PASO 1
Comenzando en la fuente, seidentifica el conjunto N1 de todos los nodos que están conectados con ella mediante un arco con capacidad disponible positiva. Se asigna la denominación k para los nodos en N1. Etiquete cada nodo k enN1 mediante el par ordenado (ek , pk) donde:
ek = d1k = Capacidad disponible del arco que une la fuente con el nodo k
pk = Nodo antecedente al nodo k
En este paso pk = 1, puesto que se estáavanzando desde la fuente (nodo 1).
A partir de este momento se asume que el nodo fuente está etiquetado.
Si en este paso se ha etiquetado el nodo n (destino), se procede directamente al paso 5.PASO 2
Elegir el nodo en N1 con el menor índice (número); forme el conjunto N2 con aquellos nodos no etiquetados que están unidos al nodo k mediante un arco con capacidad remanente positiva. Sino hay nodos sin etiquetar, se continúa con el siguiente nodo en N1 con el menor índice. Utilice la denominación m para cada nodo en N2. Asigne una etiqueta a cada nodo no etiquetado en N2 medianteel par ordenado (em , pm) donde:
em = min { dkm , ek }
pm = k
Observe que em es el mínimo de las capacidades disponibles de los arcos desde la fuente al nodo k y desde k al nodo m. Por suparte pm denota al nodo k que antecede al nodo m.
Este procedimiento se repite para cada nodo en N1.
PASO 3
Repita el paso 2 con Nr substituyendo a Nr-1 (r = 3, 4, …, n-1)
Después de un...
Leer documento completo
Regístrate para leer el documento completo.