Алгоритм поиска блокирующего потока в ациклической сети

Жадный Алгоритм

Идея заключается в том, чтобы по одному находить пути из истока [math]s[/math] в сток [math]t[/math], пока это возможно. Обход в глубину найдёт все пути из [math]s[/math] в [math]t[/math], если из [math]s[/math] достижима [math]t[/math], а пропускная способность каждого ребра [math]c(u, v)\gt 0[/math] поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока [math]t[/math], следовательно блокирующий поток всегда найдётся.

Используя [math]dfs[/math], каждый путь находится за [math]O(E)[/math], где [math]E[/math] — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет [math]O(E)[/math] путей. Итого общая асимптотика составляет [math]O(E^2)[/math].

Удаляющий обход

Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока [math]t[/math]. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.

dfs() 
   [math]p \leftarrow [s];[/math] //путь [math]p[/math]
   [math]v \leftarrow s[/math]; //текущая вершина и указатель на вершину первого неудалённого ребра
   if(нет пути из [math]v[/math])
      if ([math]v = s[/math])
          завершить алгоритм;
      else
          удалить [math](uv)[/math] из [math]V(G)[/math]; //[math]uv[/math] - последнее ребро на пути [math]p[/math]
          удалить [math]v[/math] из [math]p[/math];
   do
      //[math]w[/math] - вершина смежная с [math]v[/math]
      [math]p \leftarrow p+[w][/math];
      [math]v \leftarrow w;[/math]
   while([math]w \ne t[/math]);
   
   [math]\delta \leftarrow [/math]min([math]c(vw) - f(vw), (vw)\in p[/math]);
   foreach [math](vw)\in p [/math]
      [math]f(vw)\leftarrow f(vw) + \delta;[/math] //увеличиваем поток вдоль пути [math]p[/math]
      [math]if[/math] (ребро [math](vw)[/math] насыщено)
         удалить [math](vw)[/math] из [math]V(G);[/math]
   dfs();

Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за [math]O(V + K)[/math], где [math]V[/math] — число вершин в графе, а [math]K[/math] — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет [math]O(P)[/math], где [math]P[/math] — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за [math]O(PV + \sum\limits_i{K_i})[/math], что, учитывая, что все указатели в сумме прошли расстояние [math]O(E)[/math], дает асимптотику [math]O(PV + E)[/math]. В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается [math]O(VE)[/math].

Замечание Если в алгоритме Диница искать блокирующий поток удаляющим обходом, то его эффективность составит [math]O(V^2E)[/math], что уже лучше эффективности алгоритма Эдмондса-Карпа [math]O(VE^2)[/math].

Алгоритм Малхотры — Кумара — Махешвари

Идея

Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее запускаем цикл, на каждой итерации которого определяем вершину [math]v[/math] с минимальным потенциалом [math]p[/math]. Затем пускается поток величины [math]p[/math] из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.

Подробное описание

Для каждой вершины [math]v[/math] вычислим входящий и исходящий потенциал: [math]p_{in}=\sum \limits_{u} c(u, v)[/math] и [math]p_{out}=\sum \limits_{u} c(u, v)[/math]. Пусть [math]p_{in}(s)=\infty[/math] и [math]p_{out}(t)=\infty[/math]. Определим потенциал или пропускную способность вершины в сети [math]p(v)=min(p_{in}(v), p_{out}(v))[/math]. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее проходить. Ясно, что через вершины с [math]p(v)=0[/math] поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленными. Если в результате появятся новые вершины с [math]p(v)=0[/math], удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с [math]p(v)\ne0[/math].

После этого приступим к построению блокирующего потока. Пусть вершина [math]v[/math] принадлежит [math]k[/math]-ому слою. Протолкнем [math]p[/math] единиц потока из вершины [math]u[/math], где [math]p(u)=min (p(w), w \in L_k)[/math], в смежные с ней вершины по исходящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины [math]v[/math]) проталкиваемый поток соберется в вершинах [math](k+1)[/math]-го слоя.

Повторим процесс отправки потока из вершин [math](k+1)[/math]-го слоя, содержащих избыток потока, в смежные им вершины [math](k+2)[/math]-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое. Заметим, что в этом слое содержится только сток, ибо все остальные вершины, ранее ему принадлежащие, были удалены из сети Диница, как вершины, имеющие нулевой потенциал. Следовательно, весь поток величины [math]p[/math], отправленный из вершины с минимальным потенциалом полностью соберется в стоке. На втором этапе вновь, начиная с вершины [math]v[/math], осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам [math](k-1)[/math]-го слоя, затем [math](k-2)[/math]-го. И так до тех пор, пока весь потока величины [math]p[/math], отправленные из вершины с минимальным потенциалом, не соберется в истоке. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину [math]p[/math].

MPM algorithm([math]s, t[/math])
{
   foreach [math](uv) \in E[/math]
     [math]f(uv) \leftarrow 0 [/math];
   Вычисляем остаточную сеть [math]R[/math];
   Найдём вспомогательный граф [math]L[/math] для [math]R[/math];
   while ([math]t \in L[/math])
   {
     while ([math]t[/math] достижима из [math]s[/math] в [math]L[/math])
     {
       найдём [math]v[/math] с миниальной пропускной способностью [math]g[/math];
       проталкиваем [math]g[/math] единиц потока из [math]v[/math] в [math]t[/math];
       проталкиваем [math]g[/math] единиц потока из [math]s[/math] в [math]v[/math];
       изменяем [math]f[/math], [math]L[/math] и [math]R[/math];
     }
     вычисляем новый вспомогательный граф [math]L[/math] из [math]R[/math];
   }
}

Асимптотика

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено [math]O(K + E_i)[/math] действий, где [math]K[/math] соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а [math]E_i[/math] — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено [math]\sum\limits_i{O(K+E_i)} = O(K^2)[/math] действий.

Источники

• e-maxx Алгоритм Диница
• The MPM Algorithm
• Алгоритм Малхотры — Кумара — Махешвари