Dinitz's algorithm: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''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.