Wtedy możemy wykonać relabel:
Function Relabel(u) height(u) = min(height(v) where r(u,v) > 0) + 1;
Algorytm Push-Relabel Cały algorytm Push-Relabel wygląda następująco: Algorithm Push-Relabel(G(V,E),s,t) while push or relabel are legal: //dopóki możemy wykonywać operację push-relabel Perform a legal push, or perform a legal relabel;
Wykonywanie tych dwóch funkcji w dowolnej kolejności, tak długo jak pozostają aktywne wierzchołki, prowadzi do obliczenia maksymalnego przepływu. Złożoność obliczeniowa tego algorytmu, gdy nie uwzględniamy kolejności wykonywania operacji push i relabel, wynosi Czynnikiem zwiększającym pesymistyczną złożoność algorytmu jest ilość wykonywanych operacji non-saturating push.
Algorytm Relabel-to-Front Algorytm Relabel-to-Front jest wariantem algorytmu Push-Relabel, który obniża złożoność obliczeniową z do Osiąga się to dzięki przeprowadzeniu procedur push i relabel w określonym porządku. Główna różnica polega na tym, że wykonujemy push and relabel na pojedynczym wierzchołku do momentu, kiedy jego nadmiar jest zupełnie wykorzystany.