В информатике , то алгоритм Эдмондс-Карп является реализацией методы Форда-Фалкерсон для вычисления максимального потока в сети потока ввремя. Алгоритм был впервые опубликован Ефимом Диницем (чье имя также транслитерируется как «EA Dinic», особенно как автор его ранних работ) в 1970 году [1] [2] и независимо опубликовано Джеком Эдмондсом и Ричардом Карпом в 1972 году [3]. Алгоритм Диника включает дополнительные методы, которые сокращают время работы до. [2]
Алгоритм
Алгоритм идентичен алгоритму Форда – Фулкерсона , за исключением того, что определяется порядок поиска при нахождении пути расширения . Найденный путь должен быть кратчайшим путем, имеющим доступную емкость. Это можно найти с помощью поиска в ширину , где мы применяем вес 1 к каждому ребру. Время работы находится, показывая, что каждый путь увеличения можно найти в раз, что каждый раз хотя бы один из края становятся насыщенными (край, который имеет максимально возможный поток), что расстояние от насыщенного края до источника вдоль пути увеличения должно быть больше, чем в последний раз, когда он был насыщен, и что длина не превышает . Еще одно свойство этого алгоритма состоит в том, что длина кратчайшего пути увеличения монотонно увеличивается. Доступное доказательство можно найти во введении в алгоритмы . [4]
Псевдокод
Алгоритм EdmondsKarp является вход : граф (граф [v] должен быть списком ребер, выходящих из вершины v в исходном графе, и их соответствующих построенных обратных ребер, которые используются для обратного потока. Каждое ребро должно иметь пропускную способность, поток, источник и сток в качестве параметров , а также указатель на обратное ребро.) s (Исходная вершина) t (Приемная вершина) вывод : расход (значение максимального расхода) flow: = 0 (Инициализировать поток до нуля) repeat (Выполнить поиск в ширину (bfs), чтобы найти кратчайший путь st. Мы используем 'pred' для хранения ребра, взятого для достижения каждой вершины, чтобы мы могли восстановить путь потом) q: = queue () q.push (s) pred: = array (graph.length) пока не пусто (q) cur: = q.pull () для ребра e в графе [cur] do, если pred [et] = null и et ≠ s и e.cap> e.flow, то pred [et]: = e 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 e.flow: = e.flow + df e.rev.flow: = e.rev.flow - df поток: = поток + df до тех пор, пока pred [t] = null (т. е. пока не будет найден путь расширения), обратный поток
Пример
Для сети из семи узлов, источника A, приемника G и пропускной способности, как показано ниже:
В парах написано по краям, - текущий поток, а это емкость. Остаточная емкость от к является , общая мощность за вычетом расхода, который уже используется. Если чистый поток от к отрицательный, он увеличивает остаточную емкость.
Вместимость | Дорожка | Результирующая сеть |
---|---|---|
Обратите внимание, как длина пути увеличения, найденного алгоритмом (выделено красным), никогда не уменьшается. Найденные пути - кратчайшие из возможных. Найденный поток равен пропускной способности на минимальном разрезе на графике, разделяющем источник и сток. В этом графе есть только один минимальный разрез, разбивающий узлы на множества а также , с емкостью
Заметки
- ^ Динич, Е. А. (1970). «Алгоритм решения задачи о максимальном потоке в сети с оценкой мощности». Советская математика - Доклады . Доклады. 11 : 1277–1280.
- ^ а б Ефим Диниц (2006). «Алгоритм Диница: исходная версия и версия Эвена» (PDF) . В Одед Гольдрайх ; Арнольд Л. Розенберг; Алан Л. Селман (ред.). Теоретическая информатика: очерки памяти Шимона Эвена . Springer. С. 218–240. ISBN 978-3-540-32880-3.
- ^ Эдмондс, Джек ; Карп, Ричард М. (1972). «Теоретические улучшения алгоритмической эффективности для задач сетевого потока» (PDF) . Журнал ACM . 19 (2): 248–264. DOI : 10.1145 / 321694.321699 . S2CID 6375478 .
- ^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2009). «26,2». Введение в алгоритмы (третье изд.). MIT Press. С. 727–730. ISBN 978-0-262-03384-8.CS1 maint: несколько имен: список авторов ( ссылка )
Рекомендации
- Алгоритмы и сложность (см. Стр. 63–69). https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html