Алгоритм поиска блокирующего потока в ациклической сети
Содержание
Жадный Алгоритм
Идея заключается в том, чтобы по одному находить пути из истока
в сток , пока это возможно. найдёт все пути из в , если из достижима , а пропускная способность каждого ребра поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока , следовательно блокирующий поток всегда найдётся.Используя
каждый путь находится за , где — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет путей. Итого общая асимптотика составляет .Удаляющий обход
Аналогично предыдущей, однако удалять в процессе обхода в глубину из графа все "лишние" рёбра, т.е. рёбра, вдоль которых не получится дойти до стока
. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). Корректность при этом сохраняется, так же согласно предыдущему пункту.int dfs (int v, int flow) { if (!flow) return 0; if (v == t) return flow; for (int & to=ptr[v]; to<n; ++to) { if (d[to] != d[v] + 1) continue; int pushed = dfs (to, min (flow, c[v][to] - f[v][to])); if (pushed) { f[v][to] += pushed; return pushed; } } return 0; } ..................................... while (pushed = dfs(s, INF)) flow += pushed;
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за блокирующего потока будет , где — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за , что, учитывая, что все указатели в сумме прошли расстояние , дает асимптотику . В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается .
, где — число вершин в графе, а — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одногоЗамечание Если в алгоритме Диница искать блокирующий поток удаляющим обходом, то его эффективность составит , что уже лучше эффективности алгоритма Эдмондса-Карпа .
Алгоритм узкого места
Идея
Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина
с минимальным потенциалом . Затем пускается поток величины из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.Подробное описание
Для каждой вершины вычислим входящий и исходящий потенциал вершин — сумму пропускных способностей
дуг сети Диница, входящих и исходящих из вершины соответственно. Входящий потенциал истока и исходящий потенциал стока положим равными бесконечности. Определим потенциал или пропускную способность вершины в сети как минимум из ее входящего и исходящего потенциалов. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее проходить. Ясно, что через вершины с нулевым потенциалом поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленными. Если в результате появятся новые вершины с нулевым потенциалом, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с ненулевым потенциалом.После этого приступим к построению блокирующего потока. Пусть вершина
принадлежит -ому слою. Протолкнем единиц потока из вершины с минимальным потенциалом в смежные с ней вершины по исходящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины ) проталкиваемый поток соберется в вершинах -го слоя. Повторим процесс отправки потока из вершин -го слоя, содержащих избыток потока, в смежные им вершины -го слоя. И так до тех пор, пока весь поток не соберется в последнем слое. Заметим, что в этом слое содержится только сток, ибо все остальные вершины, ранее ему принадлежащие, были удалены из сети Диница, как вершины, имеющие нулевой потенциал. Следовательно, весь поток величины , отправленный из вершины с минимальным потенциалом полностью соберется в стоке. На втором этапе вновь, начиная с вершины , осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам -го слоя, затем -го. И так до тех пор, пока весь потока величины , отправленные из вершины с минимальным потенциалом, не соберется в истоке. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину .
= 0; Вычисляем остаточную сеть ; Найдём вспомогательный граф для ; ( достижима из в ) найдём с миниальной пропускной способностью ; проталкиваем единиц потока из в ; проталкиваем единиц потока из в ; изменяем , и ; вычисляем новый вспомогательный граф из ;
Асимптотика
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено
действий, где соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено действий.Замечание Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.