:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Графы и маршруты » Алгоритмы нахождения максимального потока » Алгоритм Эдмондса-Карпа, локально-максимального увеличения
  Алгоритм Эдмондса-Карпа, локально-максимального увеличения



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

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

 

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

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

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

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

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

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

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