1632
правки
Изменения
м
rollbackEdits.php mass rollback
В результате подъёма высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.
'''function''' relabel('''Node''' u) h(u) = min({h(v): f(u, v) - c(u, v) < 0) } + 1
== Схема алгоритма ==
'''function''' initializePreflow('''Node''' s)
'''for''' u <tex> \in </tex> V
h(u) = 0
После инициализации будем выполнять операции проталкивания и подъёма в произвольном порядке. Утверждается, что количество данных операций конечно, и после завершения работы алгоритма наш предпоток является максимальным потоком.
'''function''' pushRelabelMaxFlow('''Node''' s, '''Node''' t)
initializePreflow(s)
'''while''' e(u) > 0 '''and''' (h(u) = h(v) + 1 '''or''' <tex> \forall </tex> (u, v) <tex>\in </tex> E_f<tex>\quad</tex> h(u) <tex> \leqslant</tex> h(v))
'''if''' e(u) > 0 '''and''' h(u) = h(v) + 1
push(u, v)
'''if''' e(u) > 0 '''and''' <tex> \forall </tex> (u, v) <tex>\in </tex> E_f<tex>\quad</tex> h(u) <tex> \leqslant</tex> h(v)
relabel(u)
[[Файл:OrGraphPush0.png|545px|left|Пример сети.]] [[Файл:OrGraphPush1.png|545px|right|Сеть после запуска потока, остаточная сеть, применение операции <tex>\mathrm{relabel}</tex>.]][[Файл:OrGraphPush2.png|545px|left|Применение операции <tex>\mathrm{push}</tex>.]]
== Корректность алгоритма ==
