Изменения
Новая страница: «==Жадный Алгоритм== ===Идея=== Идея заключается в том, чтобы по одному находить пути из <tex>s</tex> …»
==Жадный Алгоритм==
===Идея===
Идея заключается в том, чтобы по одному находить пути из <tex>s</tex> в <tex>t</tex>, пока это возможно.
===Асимптотика===
Используя <tex>dfs</tex> каждый путь находится за <tex>O(V)</tex>. Поскольку каждый пусть насыщает как минимум одно ребро, всего будет <tex>O(V)</tex> путей. Итого общая асимптотика составляет <tex>O(V^2)</tex>.
==Удаляющий обход==
===Идея===
По-прежнему по одному находятся пути из <tex>s</tex> в <tex>t</tex>, но применяется следующая оптимизация: в процессе обхода в глубину удаляются все ребра, вдоль которых нельзя дойти до стока. То есть, если для текущей вершины <tex>v dfs(v) = false</tex>, нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину.
===Асимптотика===
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>K</tex> - число продвижения указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + PK)</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается <tex>O(VE)</tex>.
<b>Замечание</b> Если в алгоритме Диница искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности алгоритма Эдмондса-Карпа <tex>(O(VE^2))</tex>.
==Алгоритм узкого места==
===Идея===
Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>ρ</tex>. Затем пускается поток величины <tex>ρ</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
===Асимптотика===
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(V + E_i)</tex> действий, где <tex>V</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum_i{O(V+E_i)} = O(V^2)</tex> действий.
<b>Замечание</b> Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.
==Волновой алгоритм==
Используя предпотоки, позволяет найти блокирующий поток за <tex>O(V^2)</tex>. Модификация алгоритма Диница, основанная на этом алгоритме, называется алгоритмом Карзанова.
==Источники==
* http://ru.wikipedia.org
* http://e-maxx.ru
* http://algolist.manual.ru
===Идея===
Идея заключается в том, чтобы по одному находить пути из <tex>s</tex> в <tex>t</tex>, пока это возможно.
===Асимптотика===
Используя <tex>dfs</tex> каждый путь находится за <tex>O(V)</tex>. Поскольку каждый пусть насыщает как минимум одно ребро, всего будет <tex>O(V)</tex> путей. Итого общая асимптотика составляет <tex>O(V^2)</tex>.
==Удаляющий обход==
===Идея===
По-прежнему по одному находятся пути из <tex>s</tex> в <tex>t</tex>, но применяется следующая оптимизация: в процессе обхода в глубину удаляются все ребра, вдоль которых нельзя дойти до стока. То есть, если для текущей вершины <tex>v dfs(v) = false</tex>, нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину.
===Асимптотика===
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>K</tex> - число продвижения указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + PK)</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается <tex>O(VE)</tex>.
<b>Замечание</b> Если в алгоритме Диница искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности алгоритма Эдмондса-Карпа <tex>(O(VE^2))</tex>.
==Алгоритм узкого места==
===Идея===
Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>ρ</tex>. Затем пускается поток величины <tex>ρ</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
===Асимптотика===
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(V + E_i)</tex> действий, где <tex>V</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum_i{O(V+E_i)} = O(V^2)</tex> действий.
<b>Замечание</b> Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.
==Волновой алгоритм==
Используя предпотоки, позволяет найти блокирующий поток за <tex>O(V^2)</tex>. Модификация алгоритма Диница, основанная на этом алгоритме, называется алгоритмом Карзанова.
==Источники==
* http://ru.wikipedia.org
* http://e-maxx.ru
* http://algolist.manual.ru
