Алгоритм проталкивания предпотока

Алгоритм проталкивания предпотока решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда-Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время . Некоторые усовершенствования ещё ускоряют алгоритм: правило выбора вершин «поднять в начало» - до , выбор высшей активной вершины - до , реализация с использованием структуры данных Сеанора (Seanor) и Тарьяна - до . Впервые был опубликован в 1986 году Гольдбергом (Andrew W. Goldberg) и Тарьяном..