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