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

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

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

Алгоритм

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

Ограничения мощности	$\forall (u,v)\in E:\ f(u,v)\leq c(u,v)$	Поток вдоль ребра не может превышать его пропускную способность.
Косая симметрия	$\forall (u,v)\in E:\ f(u,v)=-f(v,u)$	Чистый поток от u к v должен быть противоположен чистому потоку от v к u (см. пример).
Сохранение потока	$\forall u\in V:u\neq s{\text{ and }}u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0$	Чистый поток к узлу равен нулю, за исключением источника, который «производит» поток, и приемника, который «потребляет» поток.
Значение(ф)	$\sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)$	Поток, выходящий из s, должен быть равен потоку, приходящему в t .

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

Algorithm Ford–Fulkerson

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

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

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

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

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

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

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

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

Сложность

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

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

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

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

Шаг	Проточная сеть
Начальная проточная сеть.
Поток направляется по увеличивающему пути $A,B,C,D$. Здесь узким местом является $B$– $C$ край, поэтому возможна только одна единица потока.
Здесь одна единица потока направляется по увеличивающему пути. $A,C,B,D$. В этом случае поток «отталкивается» от $C$ к $B$. Поток в $C$ которое изначально пришло из $B$ теперь происходит от $A$, и $B$ теперь можно свободно отправлять поток в $D$ напрямую. В результате $B$– $C$ край остается с нулевым потоком, но общий поток увеличивается на единицу.
Промежуточные этапы 1998 года здесь опущены.
Конечная проточная сеть с общим потоком 2000 единиц.

Незавершающийся пример

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

Шаг	Дополняющий путь	Отправленный поток	Остаточные мощности
			$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$1$
1	$\{s,v_{2},v_{3},t\}$	$1$	$r^{0}$	$r^{1}$	$0$
2	$p_{1}$	$r^{1}$	$r^{0}-r^{1}=r^{2}$	$0$	$r^{1}$
3	$p_{2}$	$r^{1}$	$r^{2}$	$r^{1}$	$0$
4	$p_{1}$	$r^{2}$	$0$	$r^{1}-r^{2}=r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

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

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

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

import collections


class Graph:
    """
    This class represents a directed graph using
    adjacency matrix representation.
    """

    def __init__(self, graph):
        self.graph = graph  # residual graph
        self.row = len(graph)

    def bfs(self, s, t, parent):
        """
        Returns true if there is a path from
        source 's' to sink 't' in residual graph.
        Also fills parent[] to store the path.
        """

        # Mark all the vertices as not visited
        visited = [False] * self.row

        # Create a queue for BFS
        queue = collections.deque()

        # Mark the source node as visited and enqueue it
        queue.append(s)
        visited[s] = True

        # Standard BFS loop
        while queue:
            u = queue.popleft()

            # Get all adjacent vertices of the dequeued vertex u
            # If an adjacent has not been visited, then mark it
            # visited and enqueue it
            for ind, val in enumerate(self.graph[u]):
                if (visited[ind] == False) and (val > 0):
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        # If we reached sink in BFS starting from source, then return
        # true, else false
        return visited[t]

    # Returns the maximum flow from s to t in the given graph
    def edmonds_karp(self, source, sink):
        # This array is filled by BFS and to store path
        parent = [-1] * self.row

        max_flow = 0  # There is no flow initially

        # Augment the flow while there is path from source to sink
        while self.bfs(source, sink, parent):
            # Find minimum residual capacity of the edges along the
            # path filled by BFS. Or we can say find the maximum flow
            # through the path found.
            path_flow = float("Inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            # Add path flow to overall flow
            max_flow += path_flow

            # update residual capacities of the edges and reverse edges
            # along the path
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

См. также

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

Ссылки

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Раздел 26.2: Метод Форда – Фулкерсона». Введение в алгоритмы (второе изд.). MIT Press и МакГроу-Хилл. стр. 651–664. ISBN  0-262-03293-7 .
• Джордж Т. Хайнеман; Гэри Поллис; Стэнли Селков (2008). «Глава 8: Алгоритмы сетевых потоков». Коротко об алгоритмах . Орейли Медиа . стр. 226–250. ISBN  978-0-596-51624-6 .
• Джон Кляйнберг ; Ева Тардос (2006). «Глава 7: Расширение задачи о максимальном потоке» . Алгоритм проектирования . Пирсон Образование. стр. 378–384 . ISBN  0-321-29535-8 .
• Самуэль Гутекунст (2019). МАШИНОСТРОЕНИЕ 1101 . Корнелльский университет.
• Бэкман, Спенсер; Хьюнь, Тони (2018). «Трансфинитный Форд – Фулкерсон в конечной сети». Вычислимость . 7 (4): 341–347. arXiv : 1504.04363 . дои : 10.3233/COM-180082 . S2CID   15497138 .

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

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

СМИ, связанные с алгоритмом Форда-Фалкерсона, на Викискладе?