Изменения

Для заданной Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]], в которой в качестве дополняющего пути выбирается [[Обход в ширину |кратчайший по рёбрам путь]] в остаточной сети (длины всех рёбер равны <tex>1</tex>G). === Описание === # Положим все потоки равными нулю. Остаточная сеть изначально совпадает с исходной сетью.# В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.# Пускаем через найденный путь (V, E, cон называется '''увеличивающим путём''' или '''увеличивающей цепью''')максимально возможный поток:## На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью <tex>\mathrm{c_{min}}</tex> алгоритм Эдмондса-Карпа находит .## Для каждого ребра на найденном пути увеличиваем поток максимальной величины из заданного истока на <tex>s\mathrm{c_{min}}</tex> , а в заданный сток противоположном ему — уменьшаем на <tex>t\mathrm{c_{min}}</tex> за .## Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.# Возвращаемся на шаг 2. ===Сложность===Сложность алгоритма Эдмондса-Карпа равна <tex>O(V EVE^2)</tex>.

'''Edmonds_Karpfunction''' EdmondsKarp(G, s, t):

'''do''' <tex>f[u,v] \leftarrow 0</tex> <tex>f[v,u] \leftarrow 0</tex>

'''do''' <tex>c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}</tex> '''for''' (для) каждого ребра <tex>(u,v) \in p</tex> '''do''' <tex>f[u,v] \leftarrow f[u,v] + c_f(p)</tex> <tex>f[v,u] \leftarrow -f[u,v]</tex>

Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]]. На каждой итерации цикла <tex>\mathrm {while}</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует никакого вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.

Если в сети <tex>G(V,E)</tex> с источником истоком <tex>s</tex> и стоком <tex>t</tex> увеличение потока производится вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>, то для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.

По выбору <tex>v</tex> и из предыдущего утверждения получаем, что <tex>\delta'_f (s, u) \ge geqslant\delta_f(s,u)</tex>.

Рассмотрим множество ребер рёбер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные ребра рёбра критическими. Покажем, что каждое из <tex>|E|</tex> ребер рёбер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические ребра рёбра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.

Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен уменьшено по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \le leqslant \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \ge geqslant \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.

Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>\dfrac{(|V| -2)/}{2 } = \dfrac{|V|/}{2 } - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра рёбра в остаточной сети, то общее количество критических ребер рёбер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex> можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_KarpEdmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>.  == Пример графа, на котором алгоритм дает плохую асимптотику ==[[Файл:MaxFlowWorstCase.png|365px|thumb|right|«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]] Заметим также, что сущетсвует существует ''сеть "грибок"''<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.Рассмотрим этот случай более подробно. Норман Заде (англ. ''Norman Zadeh'') описал примеры, которые позволяют добиться асимптотики <tex>\Omega(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>\Omega(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.Разделим все вершины (за исключением <tex>s</tex> и <tex>t</tex>) на подмножества:*<tex>S={s_1,\ldots,s_k}</tex> — множество вершин, в которые входят рёбра из <tex>s</tex> с пропускной способностью <tex>k</tex>,*<tex>T={t_1,\ldots,t_k}</tex> — множество вершин, из которых исходят рёбра в <tex>t</tex> с пропускной способностью <tex>k</tex>, *<tex>U={u_1,\ldots,u_{2p}}</tex> — множество вершин, достижимых из <tex>s</tex> по рёбрам с бесконечной пропускной способностью (не используя иные рёбра),*<tex>V={v_1,\ldots,v_{2p}}</tex> — множество вершин, из которых можно достигнуть <tex>t</tex> по рёбрам с бесконечной пропускной способностью (не используя иные рёбра). <tex>S</tex> и <tex>T</tex> содержат <tex>k</tex> вершин, <tex>U</tex> и <tex>V</tex> содержат <tex>2p</tex> вершин. Где <tex>k</tex> и <tex>p</tex> фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества <tex>S</tex> и <tex>T</tex>), имеет единичную пропускную способность; пунктирные рёбра имеют бесконечную пропускную способность; остальные рёбра(в форме дуги) имеют пропускную способность <tex>k</tex>.В начале работы алгоритма путь увеличиться <tex>k^2</tex> раз по пути (<tex>s</tex>, <tex>S</tex>, <tex>T</tex>, <tex>t</tex>), длина которого равна трем. После этого остаточная сеть будет содержать обратные рёбра из <tex>T</tex> в <tex>S</tex>, и алгоритм выберет еще <tex>k^2</tex> путей <tex>(s, u_1, u_2, T, S, v_2, v_1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t)</tex> длины <tex>11</tex> и так далее.:Число вершин в сети: <tex>n = 2\cdot k + 4\cdot p + 2</tex>. :Число рёбер: <tex> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>. Нетрудно заметить, что число удлиняющих путей <tex> a = k^2\cdot (p+1)</tex>.Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути. [[Файл:InGraph.png|300px|thumb|left| Изначальный граф, нулевой поток]][[Файл:SecondStage.png|300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]][[Файл:ThirdStageEdmunds karp.png|300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]                              == См. также ==*[[Определение сети, потока]]*[[Обход в ширину]]*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]

== Литература Источники информации ==