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

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

Алгоритм

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

Псевдокод

алгоритм ЭдмондсКарп является    Вход: график (граф [v] должен быть списком ребер, выходящих из вершины v в                 исходный график и их соответствующие построенные обратные ребра                 которые используются для обратного потока.                 Каждое ребро должно иметь в качестве параметров мощность, поток, источник и сток.                 а также указатель на обратный край.)        s (Исходная вершина)        т (Вершина раковины)    выход:        поток (Значение максимального расхода)        расход: = 0 (Инициализировать поток до нуля)    повторение        (Выполните поиск в ширину (bfs), чтобы найти кратчайший путь s-t.         Мы используем 'pred' для хранения ребра, сделанного, чтобы добраться до каждой вершины,         чтобы потом мы могли восстановить путь)        q: = очередь() q.push (s) pred: = множество(длина графика) пока нет пустой (q) cur: = q.pull () за Edge e в график [cur] делать                если пред [e.t] = ноль и e.t ≠ s и e.cap> e.flow тогда                    pred [e.t]: = e q.push (e.t) если нет (пред [t] = ноль) тогда            (Мы нашли дополнительный путь.             Посмотрите, сколько потока мы можем отправить)             df: = ∞            за (e: = pred [t]; e ≠ null; e: = pred [e.s]) делать                df: = мин(df, e.cap - e.flow) (И обновите края на это количество)            за (e: = pred [t]; e ≠ null; e: = pred [e.s]) делать                e.flow: = e.flow + df e.rev.flow: = e.rev.flow - df flow: = flow + 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 {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))\\=&\min(3-0,2-0,1-0)=\\=&\min(3,2,1)=1\end{aligned}}}$	${\displaystyle A,D,E,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,6-0,9-0)\\=&\min(2,6,9)=2\end{aligned}}}$	${\displaystyle A,D,F,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-0,4-0,1-0,6-2,9-2)\\=&\min(3,4,1,4,7)=1\end{aligned}}}$	${\displaystyle A,B,C,D,F,G}$
${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,4-1,2-0,0-(-1),6-3,9-3)\\=&\min(2,3,2,1,3,6)=1\end{aligned}}}$	${\displaystyle A,B,C,E,D,F,G}$

Обратите внимание, как длина расширение пути найденное алгоритмом (красным) никогда не уменьшается. Найденные пути - кратчайшие из возможных. Найденный поток равен пропускной способности через минимальный разрез в графе, разделяющем источник и сток. В этом графе есть только один минимальный разрез, разбивающий узлы на множества ${\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. Ефим Диниц (2006). «Алгоритм Диница: исходная версия и версия даже» (PDF). В Одед Гольдрайх; Арнольд Л. Розенберг; Алан Л. Селман (ред.). Теоретическая информатика: очерки памяти Шимон Эвен. Springer. С. 218–240. ISBN  978-3-540-32880-3.
3. Эдмондс, Джек; Карп, Ричард М. (1972). «Теоретические улучшения алгоритмической эффективности для задач сетевого потока» (PDF). Журнал ACM. 19 (2): 248–264. Дои:10.1145/321694.321699.
4. Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Штайн (2009). "26.2". Введение в алгоритмы (третье изд.). MIT Press. С. 727–730. ISBN  978-0-262-03384-8.

Рекомендации

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