Алгоритм "поднять-в-начало"

Алгоритм "поднять-в-начало" (relabel-to-front) основан на методе проталкивание предпотока, но из-за тщательного выбора порядка выполнения операций проталкивания и подъема, время выполнения данного алгоритма составляет [math]O(V^{3})[/math], что асимптотически не хуже, чем [math]O(V^{2}E)[/math].

Определения

[math]G = (V, E)[/math] - сеть с истоком [math]s[/math] и стоком [math]t[/math], [math]f[/math] - предпоток в [math]G[/math], [math]h[/math] - функция высоты.

Определение:

Допустимое ребро (admissible edge) - ребро [math]uv[/math], у которого [math]c_{f}(u, v) \gt 0[/math] и [math]h(u) = h(v) + 1[/math]. В противном случае [math]uv[/math] называется недопустимым (inadmissible).

Определение:

Допустимая сеть (admissible network) - сеть [math]G_{f, h} = (V, E_{f, h})[/math], где [math]E_{f, h}[/math] - множество допустимых ребер.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
• Алгоритм проталкивания предпотока — Википедия