Dinitz's algorithm

Материал из WEGA
Версия от 15:54, 31 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Dinitz's algorithm''' --- алгоритм Диница. This is the algorithm for finding maximum ''flows'' in undirected graphs that repeatedly augments the …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Dinitz's algorithm --- алгоритм Диница.

This is the algorithm for finding maximum flows in undirected graphs that repeatedly augments the current flow by a blocking flow in the graph induced by the residual arcs on shortest paths from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math]. It is known that Dinitz's algorithm terminates in [math]\displaystyle{ \min(n^{2/3}m^{1/2}) }[/math] iterations.