Изменения
→Алгоритм
== Алгоритм ==
Инициализируем предпоток и высоты, с помощью операции [[Метод проталкивания предпотока#Схема алгоритма|<tex>\mathtt{initializePreflow}</tex>]]. Список <tex>L</tex> {{---}} список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель <tex>current</tex> каждой вершины <tex>u</tex>, чтобы он указывал на первую вершину в списке <tex>u</tex>.
Пройдем по списку <tex>L</tex>, разгружая вершины, начиная с первой. И если операция <tex>discharge</tex> изменила высоту вершины, то перемещаем ее в начало списка <tex>L</tex>. Передвинем указатель на следующую вершину списке <tex>L</tex>. Если после разгрузки была изменена высота, то берем следующую вершину в новом списке <tex>L</tex>.
'''function''' <tex>\mathtt{relabelToFront}(s, t): </tex>''' <tex>\mathtt{initializePreflow(s)}</tex> <tex>L = V / \setminus \{s, t\}</tex> '''for''' u <tex>u \in V </tex> V <tex>\setminus</ tex> <tex>\{s, t\}</tex> <tex>current[u] = head[N[u]]</tex> <tex>u = head[L]</tex> '''while''' <tex>u != \ne null</tex> <tex>oldHeight = h[u]</tex> <tex>\mathtt{discharge(u)}</tex> '''if''' <tex>h[u] > oldHeight</tex> передвинуть <tex>u </tex> в начало списка <tex>L</tex> <tex>u = nextVertex[u]</tex>
В приведенном псевдокоде предполагается, что для каждой вершины <tex>u</tex> уже создан список <tex>N[u]</tex>.
<tex>nextVertex[u]</tex> возвращает хранит вершину, следующую за <tex>u</tex> в списке <tex>L</tex>. Если <tex>u</tex> {{---}} последняя вершина в списке, то <tex>nextVertex[u] = null</tex>.
'''Инвариант цикла''': "при каждом выполнении условия вхождения в цикл '''while''' вершины в списке <tex>L</tex> топологически упорядочены в допустимой сети <tex>G_{f, h} = (V, E_{f, h})</tex>, и ни одна вершина, стоящая в списке перед <tex>u</tex>, не имеет избыточного потока".
