El algoritmo de reetiquetado al frente se usa para encontrar el flujo máximo en la red. El algoritmo de reetiquetado al frente es más eficiente que el método genérico de reetiquetado de inserción . En el método de inserción y reetiquetado, podemos aplicar las operaciones básicas de inserción y reetiquetado en cualquier orden. El algoritmo de reetiquetado al frente elige el orden cuidadosamente y administra las estructuras de datos de la red de manera eficiente.
Primero, necesitamos entender las operaciones básicas, es decir, empujar y volver a etiquetar :
cada vértice en la red tiene 2 variables asociadas, que son la variable de altura (h) y el exceso de flujo (e) .
- Empuje: si un vértice tiene exceso de flujo y hay un Node adyacente con menor altura (en el gráfico residual), entonces empujamos el flujo desde el vértice al Node de menor altura.
- Volver a etiquetar: si un vértice tiene un exceso de flujo y no hay ningún Node adyacente con una altura más baja disponible, usamos la operación de volver a etiquetar para aumentar la altura del vértice para que pueda realizar la operación de inserción.
El algoritmo de reetiquetado al frente mantiene una lista de vértices en la red. Comienza desde el principio de la lista y selecciona repetidamente un vértice u desbordado y realiza una operación de descarga en él.
La operación de descarga está realizando la operación de empujar y volver a etiquetar hasta que el vértice u no tenga exceso de flujo positivo (e).
Si se vuelve a etiquetar un vértice, se mueve al frente de la lista y el algoritmo escanea nuevamente.
Algoritmo:
- Inicialice el preflujo y las alturas con los mismos valores que en el algoritmo genérico push-relabel .
- Inicialice la lista L que contiene todos los vértices excepto fuente y sumidero .
- Inicialice el puntero actual de cada vértice u al primer vértice en la lista de vecinos de u N . La lista de vecinos N contiene aquellos vértices para los que existe una arista residual.
- Mientras que el algoritmo llega al final de la lista L .
- Seleccione el vértice u de la lista L y realice la operación de descarga.
- Si fue reetiquetado por descarga , mueva u al frente de la lista.
- Si u se movió al frente de la lista, el vértice en la siguiente iteración es el que sigue a u en su nueva posición en la lista.
Ejemplo:
Considere la red de flujo dada. A la derecha se muestra la lista inicial L=(B, C) donde inicialmente u=B.
Después de la operación de inicialización del preflujo. Debajo de cada vértice en la lista L está su lista de vecinos N con el vecino actual encerrado en un círculo.
El vértice B se somete a la operación de descarga ya que tiene un exceso de flujo 3 (e = 3). El vértice B no tiene un Node con una altura más baja, por lo que realiza una operación de reetiquetado (h = 1) y empuja el flujo 1 al vértice C.
El vértice B aún tiene exceso de flujo 2 (e=2), por lo que realiza la operación de reetiquetado (h=5) y empuja el flujo 2 al vértice A. Dado que el vértice B está reetiquetado, permanece al frente de la lista. Ahora el vértice C se somete a la operación de descarga ya que tiene un exceso de flujo 1(e=1).
El vértice C realiza la operación de reetiquetado (h=1) y empuja el flujo 1 al Node D. Dado que el vértice C realizó la operación de reetiquetado, se mueve al frente de la lista.
El vértice B ahora sigue al vértice C en L pero B no tiene exceso de flujo. RELABEL-TO-FRONT ha llegado al final de la lista L y termina. No hay vértices desbordantes, por lo que el preflujo es un flujo máximo. Aquí el flujo máximo es 1.
Complejidad de tiempo: se ejecuta en tiempo O(V 3 ) en la red G = (V, E) . Por lo tanto, es más eficiente que el algoritmo genérico push-relabel que se ejecuta en tiempo O(V 2 E) .