Dinitz's algorithm: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Dinitz's algorithm''' --- алгоритм Диница. This is the algorithm for finding maximum ''flows'' in undirected graphs that repeatedly augments the …») |
(нет различий)
|
Текущая версия от 15:54, 31 марта 2011
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.