Алгоритм Эдмондса–Карпа

Алгоритм вычисления максимального потока в транспортной сети

В информатике алгоритм Эдмондса–Карпа представляет собой реализацию метода Форда–Фалкерсона для вычисления максимального потока в потоковой сети за время. Алгоритм был впервые опубликован Ефимом Диницем в 1970 году ^{[1] [2]} и независимо опубликован Джеком Эдмондсом и Ричардом Карпом в 1972 году ^{[3] .} Алгоритм Диница включает дополнительные методы, которые сокращают время выполнения до . ^[2] ${\displaystyle O(|V||E|^{2})}$ ${\displaystyle O(|V|^{2}|E|)}$

Алгоритм

Алгоритм идентичен алгоритму Форда-Фалкерсона , за исключением того, что порядок поиска при поиске увеличивающего пути определен. Найденный путь должен быть кратчайшим путем, имеющим доступную пропускную способность. Его можно найти с помощью поиска в ширину , где мы применяем вес 1 к каждому ребру. Время выполнения находится путем показа того, что каждый увеличивающий путь может быть найден за время, что каждый раз, когда хотя бы одно из ребер становится насыщенным (ребро, которое имеет максимально возможный поток), что расстояние от насыщенного ребра до источника вдоль увеличивающего пути должно быть больше, чем в прошлый раз, когда оно было насыщено, и что длина не превышает . Другое свойство этого алгоритма заключается в том, что длина кратчайшего увеличивающего пути монотонно увеличивается. Доступное доказательство есть в Введении в алгоритмы . ^[4] ${\displaystyle O(|V||E|^{2})}$ ${\displaystyle O(|E|)}$ ${\displaystyle E}$ ${\displaystyle |V|}$

Псевдокод

Алгоритм EdmondsKarp имеет  входные данные : graph (graph[v] должен быть списком ребер, выходящих из вершины v в  исходном графе , и соответствующих им построенных обратных ребер  , которые используются для обратного потока.  Каждое ребро должно иметь пропускную способность 'cap', поток, источник 's' и сток 't'  в качестве параметров, а также указатель на обратное ребро 'rev'.) s (Исходная вершина) t (Стоковая вершина)  выход : поток (Значение максимального потока)  flow := 0 (Инициализируем flow нулем)  repeat  (Запускаем поиск в ширину (bfs), чтобы найти кратчайший путь st.  Мы используем 'pred' для хранения ребра, взятого для достижения каждой вершины,  чтобы впоследствии можно было восстановить путь) q := queue () q.push(s) pred := array (graph.length) пока  не пустой(q) и pred[t] = null текущ := q.pop() для ребра e в graph[cur] сделать  , если pred[et] = null  и et ≠ s и e.cap > e.flow тогда пред[ет] := е q.push(et) если  нет (pred[t] = null) тогда  (Мы нашли увеличивающийся путь.  Посмотрим, какой поток мы можем отправить) df := ∞  for (e := pred[t]; e ≠ null; e := pred[es]) do df := min (df, e.cap - e.flow) (И обновить ребра на эту величину)  for (e := pred[t]; e ≠ null; e := pred[es]) do эл.поток := эл.поток + df e.rev.flow := e.rev.flow - df поток := поток + df пока pred[t] = null (т.е. пока не будет найден дополнительный путь)  обратный поток

Пример

Дана сеть из семи узлов, источника A, приемника G и пропускных способностей, как показано ниже:

В парах, написанных по краям, — текущий поток, а — емкость. Остаточная емкость от до — это , общая емкость, за вычетом уже использованного потока. Если чистый поток от до отрицателен, он вносит вклад в остаточную емкость. ${\displaystyle f/c}$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$

Обратите внимание, что длина увеличивающегося пути, найденного алгоритмом (красным), никогда не уменьшается. Найденные пути являются кратчайшими из возможных. Найденный поток равен пропускной способности через минимальный разрез в графе, разделяющий источник и сток. В этом графе есть только один минимальный разрез, разделяющий узлы на множества и , с пропускной способностью ${\displaystyle \{A,B,C,E\}}$ ${\displaystyle \{D,F,G\}}$

${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }$

Примечания

1. Динич, Е.А. (1970). «Алгоритм решения задачи максимального потока в сети с оценкой мощности». Советская математика - Доклады АН СССР . 11. Доклады АН СССР: 1277–1280.
2. Yefim Dinitz (2006). "Алгоритм Диница: оригинальная версия и версия Эвена" (PDF) . В Oded Goldreich ; Arnold L. Rosenberg; Alan L. Selman (ред.). Теоретическая информатика: очерки памяти Шимона Эвена . Springer. стр. 218–240. ISBN 978-3-540-32880-3.
3. Эдмондс, Джек ; Карп, Ричард М. (1972). «Теоретические улучшения алгоритмической эффективности для проблем сетевых потоков» (PDF) . Журнал ACM . 19 (2): 248–264. doi :10.1145/321694.321699. S2CID  6375478.
4. Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн (2009). «26,2». Введение в алгоритмы (третье изд.). МТИ Пресс. стр. 727–730. ISBN 978-0-262-03384-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

Ссылки

1. Алгоритмы и сложность (см. страницы 63–69). https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html