Алгоритм локально-максимального увеличения.

 

Второй метод выбора увеличивающей цепи, предложенный Эдмондсом и Карпом в 1972 г. позволяет найти максимальный поток за O(nm²M(G)), где M(G) - . Хотя его трудоемкость и зависит логарифмически от пропускных способностей сети, на практике дает вполне приемлемые результаты. Согласно этому методу, поток изменяется вдоль цепи с наибольшей пропускной способностью.

Вновь рассмотрим метод пометок. Добавим в метку поле p – приоритет узла. На этапе инициализации алгоритма все вершины имеют нулевой приоритет. Тогда при пометки вершины y из x приоритет p будет равен max{p, p₁},  где p – текущий приоритет вершины.

 p₁ = с(y) – e(y), если дуга (x, y) согласованна

 p₁ = –e(y), если дуга (x, y) несогласованна.

Процесс пометки вершин следует продолжать до тех пор, пока все вершины не получат статус просмотренных.

 На втором этапе, при восстановлении пути из стока в источник, следует воспользоваться методами динамического программирования и выбрать путь, сумма приоритетов вершин которого максимальна.

В работе [7] показан пример оптимизации алгоритма, приводящий к оценке трудоемкости O(n²m M(G)).