Алгоритм Эдмондса-Карпа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 63: Строка 63:
 
}}
 
}}
  
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует сеть  "грибок"<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>.
+
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует '''сеть  "грибок"'''<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>.
  
[[Файл:MaxFlowWorstCase.png|365px|thumb|right| "грибок"]]
+
== Пример графа на котором алгоритм дает плохую асимптотику ==
Рассмотрим этот случай более подробно. Норман Заде(англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики <tex>O(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>O(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.
+
[[Файл:MaxFlowWorstCase.png|365px|thumb|right| "грибок" ]]
Разделим все вершины(за исключением <tex>s</tex> и <tex>t</tex> на подмножества: <tex>S</tex>={s1,,sk}, <tex>T</tex>={t1,,tk}, <tex>U</tex>={u1,,u2p} и <tex>V</tex>={v1,,v2p}. <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>.
+
Рассмотрим этот случай более подробно. Норман Заде(англ. 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>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</tex>, <tex>u1</tex>, <tex>u2</tex>, <tex>T</tex>, <tex>S</tex>, <tex>v2</tex>, <tex>v1</tex>, <tex>t</tex>) длины 7, затем путь <tex>(s, u1, u2, u3, u4, S, T, v4, v3, v2, v1, t)</tex> длины 11 и так далее...
+
Разделим все вершины (за исключением <tex>s</tex> и <tex>t</tex> на подмножества: <tex>S={s1,\ldots,sk}</tex>, <tex>T={t1,\ldots,tk}</tex>, <tex>U={u1,\ldots,u2p}</tex> и <tex>V={v1,\ldots,v2p}</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>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>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, u1, u2, T, S, v2, v1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u1, u2, u3, u4, S, T, v4, v3, v2, v1, 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>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути  
 
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути  
  

Версия 01:05, 8 января 2017

Алгоритм

Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона, в которой в качестве дополняющего пути выбирается кратчайший по ребрам путь в остаточной сети (длины всех ребер равны [math]1[/math]).

Описание

  1. Положим все потоки равными нулю. Остаточная сеть изначально совпадает с исходной сетью.
  2. В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.
  3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
    1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью [math]\mathrm{c_{min}}[/math].
    2. Для каждого ребра на найденном пути увеличиваем поток на [math]\mathrm{c_{min}}[/math], а в противоположном ему — уменьшаем на [math]\mathrm{c_{min}}[/math].
    3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
  4. Возвращаемся на шаг 2.

Сложность

Сложность алгоритма Эдмондса-Карпа равна [math]O(VE^2)[/math].

Псевдокод

function EdmondsKarp(G, s, t):
    for (для) каждого ребра [math](u,v) \in E[G][/math]
        [math]f[u,v] \leftarrow 0[/math]
        [math]f[v,u] \leftarrow 0[/math]
    while существует кратчайший путь [math]p[/math] из [math]s[/math] в [math]t[/math] в остаточной сети [math]G_f[/math]
        [math]c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}[/math]
        for [math](u,v) \in p[/math]
            [math]f[u,v] \leftarrow f[u,v] + c_f(p)[/math]
            [math]f[v,u] \leftarrow -f[u,v][/math]

Корректность алгоритма Эдмондса-Карпа

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

Оценка быстродействия

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

Предположим противное, пусть существует вершина [math]v \in V \backslash\{s,t\}[/math], что после какого-то увеличения потока длина кратчайшего пути из [math]s[/math] в [math]v[/math] уменьшилась. Обозначим потоки до и после увеличения соответственно за [math]f[/math] и [math]f'[/math]. Пусть [math]v[/math] — вершина, расстояние [math]\delta'_f(s,v)[/math] от [math]s[/math] до которой минимально и уменьшилось с увеличением потока. Имеем [math]\delta'_f(s,v) \lt \delta_f(s,v)[/math]. Рассмотрим путь [math]p = s \leadsto u \rightarrow v[/math], являющийся кратчайшим от [math]s[/math] к [math]v[/math] в [math]G'_f[/math]. Тогда верно, что [math]\delta'_f(s, u) = \delta'_f(s,v) - 1[/math].

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

Предположим [math](u, v) \in E_f[/math], тогда [math]\delta_f(s,v) \leqslant \delta_f(s, u) + 1 \leqslant \delta'_f(s,u) + 1 = \delta'_f(s, v)[/math]. Это противоречит [math]\delta'_f(s,v) \lt \delta_f(s,v)[/math].

Пусть [math](u,v) \notin E_f[/math], но известно, что [math](u,v) \in E_f'[/math]. Появление ребра [math](u,v)[/math] после увеличения потока означает увеличение потока по обратному ребру [math](v, u)[/math]. Увеличение потока производится вдоль кратчайшего пути, поэтому кратчайший путь из [math]s[/math] в [math]u[/math] вдоль которого происходило увеличения выглядит как [math]s \leadsto v \rightarrow u[/math], из чего получаем [math]\delta_f(s, v) = \delta_f(s, u) - 1 \leqslant \delta'_f(s, u) - 1 = \delta'(s, v) - 2[/math]. Данное утверждение противоречит [math]\delta'_f(s,v) \lt \delta_f(s,v)[/math]. Итак мы пришли к противоречию с существованием вершины [math]v[/math], кратчайшее расстояние до которой уменьшилось с увеличением потока.
[math]\triangleleft[/math]


Опираясь на предшествующую лемму, докажем следующую теорему, которая ограничивает сверху число итераций цикла [math]\mathrm {while}[/math] в алгоритме Эдмондса-Карпа.

Теорема:
Пусть для некоторой сети [math]G(V,E)[/math] с источником [math]s[/math] и стоком [math]t[/math] выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла [math]\mathrm {while}[/math] составляет [math]O(V E)[/math].
Доказательство:
[math]\triangleright[/math]

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

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

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

Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет [math]O(V E)[/math]. На каждой итерации цикла [math]\mathrm {while}[/math] рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла [math]\mathrm {while}[/math] также составляет [math]O(V E)[/math].
[math]\triangleleft[/math]

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла [math]\mathrm {while}[/math] можно выполнить за время [math]O(E)[/math]. Инициализация в процедуре Edmonds Karp производится за [math]O(E)[/math], следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет [math]O(V E^2)[/math]. Заметим также, что сущетсвует сеть "грибок"[1] на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет [math]\Omega(V E^2)[/math].

Пример графа на котором алгоритм дает плохую асимптотику

"грибок"

Рассмотрим этот случай более подробно. Норман Заде(англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики [math]\Omega(V^3)[/math][2]. В нашем примере алгоритм выполнит [math]\Omega(V^3)[/math] улучшений пути вне зависимости от выбора этого пути. Разделим все вершины (за исключением [math]s[/math] и [math]t[/math] на подмножества: [math]S={s1,\ldots,sk}[/math], [math]T={t1,\ldots,tk}[/math], [math]U={u1,\ldots,u2p}[/math] и [math]V={v1,\ldots,v2p}[/math]. [math]S[/math] и [math]T[/math] содержат [math]k[/math] вершин, [math]U[/math] и [math]V[/math] содержат [math]2p[/math] вершин. Где [math]k[/math] и [math]p[/math] фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества [math]S[/math] и [math]T[/math]), имеет единичную пропускную способность; пунктирные ребра имеют бесконечную пропускную способность; остальные ребра(в форме дуги) имеют пропускную способность [math]k[/math]. В начале работы алгоритма путь увеличиться [math]k^2[/math] раз по пути ([math]s[/math], [math]S[/math], [math]T[/math], [math]t[/math]), длина которого равна трем. После этого остаточная сеть будет содержать обратные ребра из [math]T[/math] в [math]S[/math], и алгоритм выберет еще [math]k^2[/math] путей [math](s, u1, u2, T, S, v2, v1, t)[/math] длины [math]7[/math], затем путь [math](s, u1, u2, u3, u4, S, T, v4, v3, v2, v1, t)[/math] длины [math]11[/math] и так далее... Число вершин в нашей сети: [math]n = 2\cdot k + 4\cdot p + 2[/math]. Число ребер: [math] m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p[/math]. Нетрудно заметить, что число удлиняющих путей [math] a = k^2\cdot (p+1)[/math] Возьмем [math]p[/math] равным [math]k - 1[/math]. В этом случае [math]n = 6 \cdot k - 2[/math] и [math]a = k^3[/math]. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути








Примечания

  1. Cтатья на TopCoder.com
  2. Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.

Источники информации