//wraca z powrotem na początek listy sąsiadów

Relabel-to-Front W algorytmie relabel-to-front w pełni rozładowujemy wierzchołek przed przejściem do kolejnego. Kolejność ta ogranicza ilość wykonywanych procedur non-saturating push.

Algorithm Relabel-to-Front(G(V,E),s,t): for each vertex v incident to s: push(s,v); // wyczerpie to krawędzie (s,v) - przepływ jest ograniczony L = v - {s,t}; // tworzy listę wierzchołków w dowolnej kolejności current = L.head; while (current != NIL): old_height = height(u); discharge(u); if height(u) > old_height: Move u to front of L current = current.next;

Złożoność obliczeniowa algorytmu relabel-to-front wynosi (dowód pomijamy). Ponownie czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest ilość procedur ‘non-saturating push’, jednak w tym przypadku ich ilość została zredukowana. Należy zauważyć, że po wykonaniu pierwszego kroku nie istnieje ścieżka z do w grafie esidualnym.

Przykładowe implementacje Implementacja w C: #include <stdlib.h> #include <stdio.h>

#define NODES 6 #define MIN(X,Y) ((X) < (Y) ?