147
правок
Изменения
м
Нет описания правки
'''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(VEV))</tex>. Можно считать модификацией Алгоритма Диница.
==Идея==
Вспомним [[Схема алгоритма Диница|Алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема Алгоритма Диница :
