25
правок
Изменения
изменен псевдокод и исправлены опечатки
==Жадный Алгоритмалгоритм==
Идея заключается в том, чтобы по одному находить пути из [[Определение_сети,_потока|истока]] <tex>s</tex> в [[Определение_сети,_потока|сток]] <tex>t</tex>, пока это возможно. [[Обход в глубину, цвета вершин| Обход в глубину]] найдёт все пути из <tex>s</tex> в <tex>t</tex>, если из <tex>s</tex> достижима <tex>t</tex>, а [[Определение_сети,_потока|пропускная способность]] каждого ребра <tex>c(u, v)>0</tex> поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока <tex>t</tex>, следовательно блокирующий поток всегда найдётся.
==Удаляющий обход==
Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое не удалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.
'''dfs''' (''v'', ''flow'') <tex>p \leftarrow [s];</tex> //путь <tex>p</tex> '''if''' (''flow'' == 0) <tex>v \leftarrow s</tex>'''return''' 0; //текущая вершина и указатель на вершину первого неудалённого ребра '''if''' (нет пути из <tex>v</tex>) if (<tex>''v '' == s</tex>'''t''') завершить алгоритм '''return''' ''flow''; else удалить <tex> '''for''' (uv)</tex> из <tex>V(G)</tex>; //<tex>uv</tex> - последнее ребро на пути <tex>p</tex> удалить <tex>v</tex> из <tex>p</tex>; do //<tex>w</tex> - вершина смежная с <tex>''u'' = ptr[''v</tex> <tex>p \leftarrow p+[w'']<'''to''' n) /tex>; <tex>v \leftarrow w;</tex>''u'' is reference value while'''if''' (''vu'' <tex>w \ne tin E</tex>); <tex>\delta \leftarrow </tex> pushed = '''dfs''' (''u'', min(<tex>flow, c(vw''vu'') - f(vw''vu''), (vw)\in p</tex>); foreach <tex> f(vw''vu'')\in p </tex>+= pushed; <tex> f(vw''uv'')\leftarrow f(vw) + \delta-= pushed; '''return''' pushed; '''return''' 0;</tex> //увеличиваем поток вдоль пути <tex>p</tex> <tex>if</tex> (ребро <tex> '''main''' (vw)</tex> насыщено) удалить <tex>(vw)</tex> из <tex>V(G) '''...''' ''flow'' = 0; ptr[''i''] = 0, ''i'' = ''1...n'';</tex> '''while''' (pushed = '''dfs''' ('''s''', ''INF'')) ''flow'' += pushed;
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>V</tex> — число вершин в графе, а <tex>K</tex> — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + \sum\limits_i{K_i})</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>.
==Алгоритм Малхотры — Кумара — Махешвари==
while (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>)
{
найдём <tex>v</tex> с миниальной минимальной пропускной способностью <tex>g</tex>;
проталкиваем <tex>g</tex> единиц потока из <tex>v</tex> в <tex>t</tex>;
проталкиваем <tex>g</tex> единиц потока из <tex>s</tex> в <tex>v</tex>;
