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

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

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

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

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

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

int dfs(int $v$, int flow) 
 if (flow == 0) 
   return 0
 if ($v$ == $t$)
   return flow
 for ($u$ = ptr[$v$] to n)  // u - ссылочный тип
   if ($vu \in E$)
     pushed = dfs($u$, min(flow, c($vu$) - f($vu$)));
     f($vu$) += pushed
     f($uv$) -= pushed
     return pushed
 return 0

 main( )
   ...
   flow = 0
   for (int i = 0 to n)
     ptr[i] = 0;
   do
     pushed = dfs ($s$, $\infty$)
     flow += pushed;
   while (pushed > 0)

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

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

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

Идея

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

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

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

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

• Повторим процесс отправки потока из вершин $(k+1)$-го слоя, содержащих избыток потока, в смежные им вершины $(k+2)$-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое, в котором содержится только сток $t$, ибо все остальные вершины, ранее ему принадлежащие, были удалены, поскольку их потенциалы нулевые. Следовательно, весь поток величины $p(v)$, отправленный из вершины $v$, где $p(v)$ - минимальный полностью соберется в $t$.

• На втором этапе вновь, начиная с вершины $v$, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам $(k-1)$-го слоя, затем $(k-2)$-го. И так до тех пор, пока весь потока величины $p(v)$, отправленные из вершины $v$, где $p(v)$ - минимальный, не соберется в истоке $s$. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину $p$.

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

Асимптотика

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

См. также

• Блокирующий поток
• Схема алгоритма Диница

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

• Алгоритм Диница. Необходимые определения.
• The MPM Algorithm
• Алгоритм Малхотры — Кумара — Махешвари
• Оригинальная публикация алгоритма Малхотры — Кумара — Махешвари.