- Алгоритм Эдмондса — Карпа
-
Алгоритм Эдмондса — Карпа
Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время O(VE2). Впервые был опубликован в 1970 году советским учёным Е. А. Диницом. Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом.
Содержание
Алгоритм
Алгоритм Эдмондса — Карпа - это вариант алгоритма Форда — Фалкерсона, при котором на каждом шаге выбирают кратчайший дополняющий путь из s в t в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину.
Описание
- Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
- В остаточной сети находим крачайший путь из источника в сток. Если такого пути нет, останавливаемся.
- Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
- На найденном пути в остаточном сети ищем ребро с минимальной пропускной способностью cmin.
- Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему - уменьшаем на cmin.
- Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
- Возвращаемся на шаг 2.
Чтобы найти кратчайший путь в графе, используем поиск в ширину:
- Создаём очередь вершин О. Вначале О состоит из единственной вершины s.
- Отмечаем вершину s как посещённую, без предка, а все остальные как непосещённые.
- Пока очередь непуста, выполняем следующие шаги:
- Удаляем первую в очереди вершину u.
- Для всех рёбер (u, v), исходящих из вершины u, таких что вершина v ещё не посещена, выполняем следующие шаги:
- Отмечаем вершину v как посещённую, с предком u.
- Добавляем вершину v в конец очереди
- Если v=t, выходим из обоих циклов: мы нашли кратчайший путь.
- Если очередь пуста, возвращаем ответ, что пути нет вообще и останавливаемся.
- Если нет, идём от t к s, каждый раз переходя к предку. Возвращаем путь в обратном порядке.
Сложность
В процессе работы алгоритм Эдмондса — Карпа будет находить каждый дополняющий путь за время O(V + E). Можно доказать, что общее число увеличений потока, выполняемое данным алгоритмом, составляет O(VE). Таким образом, сложность алгоритма Эдмондса — Карпа равна O(VE2).
Пример
Пусть задана сеть с истоком в вершине A и стоком в вершине G. На рисунке парой f / c обозначен поток по этому ребру и его пропускная способность.
Поиск в ширину
Опишем поиск в ширину на первом шаге.
- Очередь состоит из единственной вершины A. Посещена вершина A. Предков нет.
- Очередь состоит (от начала к концу) из вершин B и D. Посещены вершины A,B,D. Вершины B,D имеют предка А.
- Очередь состоит из вершин D и C. Посещены A,B,C,D. Вершины B,D имеют предка А, вершина C - предка B.
- Очередь состоит из вершин C,E,F. Посещены A,B,C,D,E,F. Вершины B,D имеют предка А, вершина C - предка B, вершины E,F - предка D.
- Вершина C удаляется из очереди: рёбра из неё ведут только в уже посещённые вершины.
- Обнаруживается ребро (E,G) и цикл останавливается. В очереди вершины (F,G). Посещены все вершины. Вершины B,D имеют предка А, вершина C - предка B, вершины E,F - предка D, вершина G - предка E.
- Идём по предкам: G->E->D->A. Возвращаем пройденный путь в обратном порядке: А->D->E->G.
Заметим, что в очередь последовательно добавляли вершины, достижимые из A ровно за 1 шаг, ровно за 2 шага, ровно за 3 шага. Кроме того, предком каждой вершины является вершина, достижимая из A ровно на 1 шаг быстрее.
Основной алгоритм
Отметим, что в процессе выполнения алгоритма длины дополняющих путей (на рисунках обозначены красным) не убывают. Это свойство выполняется благодаря тому, что мы ищем кратчайший дополняющий путь.
Алгоритм Диница
Улучшенной версией алгоритма Эдмондса-Карпа является алгоритм Диница, требующий O( | V | 2 | E | ) операций.
Назовём вспомогательной бесконтурной сетью графа G с источником s его подграф, содержащий только такие рёбра (u, v), для которых минимальное расстояние от s до v на единицу больше минимального расстояния от s до u.
Алгоритм Диница:
- Строим минимальную бесконтурную сеть остаточного графа.
- Пока в сети есть путь из s в t, выполнить следующие шаги:
- Находим кратчайший путь из s в t. Если его нет, выйти из цикла.
- На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью cmin.
- Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему - уменьшаем на cmin.
- Удаляем все рёбра, достигшие насыщения.
- Удаляем все тупики (то есть вершины, кроме стока, откуда не выходит рёбер, и вершины, кроме источника, куда рёбер не входит) вместе со всеми инцидентными им рёбрами.
- Повторяем предыдущий шаг, пока есть что удалять.
- Если найденный поток ненулевой, добавляем его к общему потоку и возвращаемся на шаг 1.
Cсылки
Литература
- Томас Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
Wikimedia Foundation. 2010.
Алгоритм Эдмондса — Алгоритм Эдмондса Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда Фалкерсона и работает за время . Впервые был опубликован в 1970 году советским учёным Е … Википедия
Алгоритм Эдмондса-Карпа — … Википедия
Алгоритм Форда — Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… … Википедия
Алгоритм Форда–Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… … Википедия
Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году израильским (бывшим русским) учёным Ефимом Диницем. Временная сложность алгоритма составляет . Получить такую оценку позволяет введение… … Википедия
Алгоритм Форда — У этого термина существуют и другие значения, см. Алгоритм Форда. Алгоритм Форда Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается… … Википедия
Форда-Фалкерсона алгоритм — Алгоритм Форда Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Карп, Ричард Мэннинг — Ричард Мэннинг Карп Richard Manning Karp … Википедия