Алгоритм Форда-Фалкерсона

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

Метод Форда–Фалкерсона или алгоритм Форда–Фалкерсона ( FFA ) — это жадный алгоритм , который вычисляет максимальный поток в потоковой сети . Иногда его называют «методом» вместо «алгоритма», поскольку подход к поиску увеличивающихся путей в остаточном графе не полностью определен ^[1] или определен в нескольких реализациях с разным временем выполнения. ^[2] Он был опубликован в 1956 году Л. Р. Фордом-младшим и Д. Р. Фулкерсоном . ^[3] Название «Форд–Фалкерсон» часто также используется для алгоритма Эдмондса–Карпа , который является полностью определенной реализацией метода Форда–Фалкерсона.

Идея алгоритма заключается в следующем: пока есть путь от источника (начальный узел) до стока (конечный узел), с доступной пропускной способностью на всех ребрах пути, мы отправляем поток по одному из путей. Затем мы находим другой путь и так далее. Путь с доступной пропускной способностью называется увеличивающим путем .

Алгоритм

Пусть будет графом, и для каждого ребра от u до v пусть будет пропускная способность и будет поток. Мы хотим найти максимальный поток от источника s до стока t . После каждого шага в алгоритме сохраняется следующее: ${\displaystyle G(V,E)}$ ${\displaystyle c(u,v)}$ ${\displaystyle f(u,v)}$

Это означает, что поток через сеть является законным потоком после каждого раунда в алгоритме. Мы определяем остаточную сеть как сеть с пропускной способностью и без потока. Обратите внимание, что может случиться так, что поток из v в u разрешен в остаточной сети, хотя запрещен в исходной сети: если и тогда . ${\displaystyle G_{f}(V,E_{f})}$ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ${\displaystyle f(u,v)>0}$ ${\displaystyle c(v,u)=0}$ ${\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}$

Алгоритм Форда–Фалкерсона

Входные данные : дана сеть с пропускной способностью c , исходным узлом s и приемным узлом t ${\displaystyle G=(V,E)}$

Выходные данные Вычислить поток f от s до t максимального значения

1. ${\displaystyle f(u,v)\leftarrow 0}$для всех краев ${\displaystyle (u,v)}$
2. В то время как существует путь p из s в t в , такой, что для всех ребер : ${\displaystyle G_{f}}$ ${\displaystyle c_{f}(u,v)>0}$ ${\displaystyle (u,v)\in p}$
   1. Находить ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v):(u,v)\in p\}}$
   2. Для каждого края ${\displaystyle (u,v)\in p}$
      1. ${\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}$( Отправить поток по пути )
      2. ${\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}$( Поток может быть «возвращен» позже )

• "←" обозначает назначение . Например, " largest ← item " означает, что значение largest изменяется на значение item .
• « return » завершает алгоритм и выводит следующее значение.

Путь на шаге 2 можно найти, например, с помощью поиска в ширину (BFS) или поиска в глубину в . Первый известен как алгоритм Эдмондса–Карпа . ${\displaystyle G_{f}(V,E_{f})}$

Если больше путей на шаге 2 не найдено, s не сможет достичь t в остаточной сети. Если S — множество узлов, достижимых s в остаточной сети, то общая пропускная способность в исходной сети ребер от S до остатка V , с одной стороны, равна общему потоку, который мы нашли от s до t , а с другой стороны, служит верхней границей для всех таких потоков. Это доказывает, что найденный нами поток является максимальным. См. также теорему о максимальном потоке и минимальном разрезе .

Если граф имеет несколько источников и стоков, действуем следующим образом: Предположим, что и . Добавляем новый источник с ребром из в каждый узел , с пропускной способностью . И добавляем новый сток с ребром из каждого узла в , с пропускной способностью . Затем применяем алгоритм Форда–Фалкерсона. ${\displaystyle G(V,E)}$ ${\displaystyle T=\{t\mid t{\text{ is a sink}}\}}$ ${\displaystyle S=\{s\mid s{\text{ is a source}}\}}$ ${\displaystyle s^{*}}$ ${\displaystyle (s^{*},s)}$ ${\displaystyle s^{*}}$ ${\displaystyle s\in S}$ ${\displaystyle c(s^{*},s)=d_{s}=\sum _{(s,u)\in E}c(s,u)}$ ${\displaystyle t^{*}}$ ${\displaystyle (t,t^{*})}$ ${\displaystyle t\in T}$ ${\displaystyle t^{*}}$ ${\displaystyle c(t,t^{*})=d_{t}=\sum _{(v,t)\in E}c(v,t)}$

Также, если узел u имеет ограничение емкости , мы заменяем этот узел двумя узлами , и ребром , с емкостью . Затем применяем алгоритм Форда–Фалкерсона. ${\displaystyle d_{u}}$ ${\displaystyle u_{\mathrm {in} },u_{\mathrm {out} }}$ ${\displaystyle (u_{\mathrm {in} },u_{\mathrm {out} })}$ ${\displaystyle c(u_{\mathrm {in} },u_{\mathrm {out} })=d_{u}}$

Сложность

Добавляя путь увеличения потока к потоку, уже установленному в графе, максимальный поток будет достигнут, когда в графе больше не будет найдено путей увеличения потока. Однако нет никакой уверенности, что эта ситуация когда-либо будет достигнута, поэтому лучшее, что можно гарантировать, — это то, что ответ будет правильным, если алгоритм завершится. В случае, если алгоритм будет работать вечно, поток может даже не сходиться к максимальному потоку. Однако эта ситуация возникает только с иррациональными значениями потока. ^[4] Когда пропускные способности являются целыми числами, время выполнения Форда–Фалкерсона ограничено (см. обозначение большого О ), где — количество ребер в графе, а — максимальный поток в графе. Это происходит потому, что каждый путь увеличения потока может быть найден за время и увеличивает поток на целую величину не менее , с верхней границей . ${\displaystyle O(Ef)}$ ${\displaystyle E}$ ${\displaystyle f}$ ${\displaystyle O(E)}$ ${\displaystyle 1}$ ${\displaystyle f}$

Разновидностью алгоритма Форда–Фалкерсона с гарантированным завершением и временем выполнения, не зависящим от максимального значения потока, является алгоритм Эдмондса–Карпа , который выполняется во времени. ${\displaystyle O(VE^{2})}$

Пример целочисленного потока

Следующий пример показывает первые шаги Форда–Фалкерсона в потоковой сети с 4 узлами, источником и стоком . Этот пример показывает наихудшее поведение алгоритма. На каждом шаге по сети отправляется только поток. Если бы вместо этого использовался поиск в ширину, потребовалось бы всего два шага. ${\displaystyle A}$ ${\displaystyle D}$ ${\displaystyle 1}$

Пример без завершения

Рассмотрим сеть потоков, показанную справа, с источником , стоком , пропускными способностями ребер , и , а также пропускной способностью всех остальных ребер некоторым целым числом . Константа была выбрана таким образом, что . Мы используем увеличивающиеся пути в соответствии со следующей таблицей, где , и . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle e_{1}=1}$ ${\displaystyle e_{2}=r=({\sqrt {5}}-1)/2}$ ${\displaystyle e_{3}=1}$ ${\displaystyle M\geq 2}$ ${\displaystyle r}$ ${\displaystyle r^{2}=1-r}$ ${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$ ${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$ ${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$

Обратите внимание , что после шага 1, а также после шага 5 остаточные пропускные способности ребер , и имеют вид , и , соответственно, для некоторых . Это означает, что мы можем использовать увеличивающие пути , и бесконечно много раз, и остаточные пропускные способности этих ребер всегда будут иметь один и тот же вид. Общий поток в сети после шага 5 равен . Если мы продолжим использовать увеличивающие пути, как указано выше, общий поток сойдется к . Однако обратите внимание, что существует поток значения , отправляя единицы потока по , 1 единицу потока по и единицы потока по . Поэтому алгоритм никогда не останавливается, и поток даже не сходится к максимальному потоку. ^[5] ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{3}}$ ${\displaystyle r^{n}}$ ${\displaystyle r^{n+1}}$ ${\displaystyle 0}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{3}}$ ${\displaystyle 1+2(r^{1}+r^{2})}$ ${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$ ${\displaystyle 2M+1}$ ${\displaystyle M}$ ${\displaystyle sv_{1}t}$ ${\displaystyle sv_{2}v_{3}t}$ ${\displaystyle M}$ ${\displaystyle sv_{4}t}$

Другой незавершающийся пример, основанный на алгоритме Евклида, приведен Бэкманом и Хюином (2018), где они также показывают, что худшее время выполнения алгоритма Форда-Фалкерсона в сети с порядковыми числами составляет . ${\displaystyle G(V,E)}$ ${\displaystyle \omega ^{\Theta (|E|)}}$

Реализация алгоритма Эдмондса–Карпа на языке Python

импортные  коллекцииКласс  График : """ Этот класс представляет собой ориентированный граф, использующий Представление матрицы смежности. """ def  __init__ ( self ,  graph ): self.graph = график  # остаточный график   self.row = len ( график )​​   определение  bfs ( self ,  s ,  t ,  parent ): """ Возвращает true, если есть путь из источник «s» для стока «t» в остаточном графе. Также заполняет parent[] для хранения пути. """ # Отметить все вершины как непосещенные посещенный  =  [ Ложь ]  *  сам . строка # Создать очередь для BFS очередь  =  коллекции . дек () # Отметить исходный узел как посещенный и поставить его в очередь очередь . добавить ( ы ) посетил [ s ]  =  Правда # Стандартный цикл BFS пока  очередь : u  =  очередь . popleft () # Получить все смежные вершины выведенной из очереди вершины u # Если соседний не был посещен, то отметьте его # посетил и поставил в очередь для  ind ,  val  в  enumerate ( self . graph [ u ]): если  ( visited [ ind ]  ==  False )  и  ( val  >  0 ): очередь . добавить ( инд .) посетил [ инд ]  =  Правда родитель [ инд ]  =  u # Если мы достигли приемника в BFS, начиная с источника, то возвращаемся # правда, иначе ложь вернуться  посетил [ t ] # Возвращает максимальный поток из s в t в заданном графе def  edmonds_karp ( сам ,  источник ,  приемник ): # Этот массив заполняется BFS и для хранения пути родитель  =  [ - 1 ]  *  сам . строка max_flow  =  0  # Изначально потока нет # Увеличивайте поток, пока есть путь от источника к приемнику  в то время как self.bfs ( источник , приемник , родитель ) :   # Найти минимальную остаточную емкость ребер вдоль # путь заполнен BFS. Или можно сказать найти максимальный поток # по найденному пути. path_flow  =  float ( "Inf" ) с  =  раковина в то время как  s  !=  источник : path_flow  =  min ( path_flow ,  self . graph [ parent [ s ]][ s ]) с  =  родитель [ с ] # Добавить поток пути к общему потоку максимальный_поток  +=  путь_потока # обновить остаточные емкости ребер и обратные ребра # по пути в  =  раковина в то время как  v  !=  источник : u  =  родитель [ v ] self.graph [ u ] [ v ] - = path_flow   сам.граф [ v ] [ u ] + = path_flow   v  =  родитель [ v ] вернуть  максимальный_поток

Смотрите также

• Теорема Берже
• Приблизительная теорема о максимальном потоке и минимальном разрезе
• Маршрутизация ограничения поворота
• Алгоритм Динича

Примечания

1. Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009). Автоматизация проектирования электроники: синтез, проверка и тестирование . Morgan Kaufmann. стр. 204. ISBN 978-0080922003.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Стейн (2009). Введение в алгоритмы . МТИ Пресс. стр. 714. ISBN. 978-0262258104.
3. Форд, Л. Р.; Фулкерсон , Д. Р. (1956). «Максимальный поток через сеть» (PDF) . Канадский журнал математики . 8 : 399–404. doi :10.4153/CJM-1956-045-5. S2CID  16109790.
4. "Алгоритм маркировки максимального потока Форда-Фалкерсона". 1998. CiteSeerX 10.1.1.295.9049 . 
5. Цвик, Ури (21 августа 1995 г.). «Наименьшие сети, на которых процедура максимального потока Форда–Фалкерсона может не завершиться». Теоретическая информатика . 148 (1): 165–170. doi : 10.1016/0304-3975(95)00022-O .

Ссылки

• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Раздел 26.2: Метод Форда–Фалкерсона". Введение в алгоритмы (Второе изд.). MIT Press и McGraw–Hill. стр. 651–664. ISBN 0-262-03293-7.
• Джордж Т. Хайнеман; Гэри Поллис; Стэнли Селков (2008). "Глава 8: Алгоритмы сетевого потока". Алгоритмы в двух словах . Oreilly Media . стр. 226–250. ISBN 978-0-596-51624-6.
• Джон Клейнберг ; Эва Тардос (2006). "Глава 7: Расширения задачи максимального потока". Разработка алгоритмов . Pearson Education. стр. 378–384. ISBN 0-321-29535-8.
• Самуэль Гутекунст (2019). ЭНГРИ 1101 . Корнелльский университет.
• Бэкман, Спенсер; Хьюн, Тони (2018). «Трансфинитный Форд–Фалкерсон в конечной сети». Computability . 7 (4): 341–347. arXiv : 1504.04363 . doi :10.3233/COM-180082. S2CID  15497138.

Внешние ссылки

• Учебное пособие, объясняющее метод Форда–Фалкерсона для решения задачи максимального потока
• Еще одна анимация Java
• Приложение Java Web Start

Медиа, связанные с алгоритмом Форда-Фалкерсона на Wikimedia Commons