Алгоритм Форда-Фалкерсона
Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.
При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.
Постановка задачи
Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.
Как работает сам алгоритм?
Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:
- Отправлять определенное количество потока из текущей вершины в соседние.
- Возвращать определенное количество потока из соседних вершин в текущую.
- В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.
- Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.
- Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.
- Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.
- А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.
- Возвращаемся обратно к нахождению пути в остаточной сети после модификации.
Разбор конкретного примера
Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.
- Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.
- Сколько потока можем провести по этому пути.
— Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:
Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.
Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .
- Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:
Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:
- На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:
Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
- На 4-ой итерации находим следующий путь в остаточной сети:
Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.
Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!
Источники
- Паша и Алгосы
- Инструмент для работы с графами
Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
Алгоритм Форда-Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
Идея
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение [math]0[/math] : [math] f(u,v) = 0 [/math] для всех [math] u, v [/math] из [math] V [/math] . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника [math]s[/math] к стоку [math]t[/math] , вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
Реализация
int dfs(int u, int Cmin): // Cmin — пропускная способность в текущем подпотоке if u = t return Cmin visited[u] = true for v in u.children auto uv = edge(u, v) if not visited[v] and uv.f < uv.c int delta = dfs(v, min(Cmin, uv.c - uv.f)) if delta > 0 uv.f += delta uv.backEdge.f -= delta return delta return 0
Оценка производительности
Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено [math]O(|E|f)[/math] , где [math]E[/math] — число рёбер в графе, [math]f[/math] — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за [math]O(E)[/math] и увеличивает поток как минимум на [math]1[/math] .
Пример несходящегося алгоритма
Рассмотрим приведённую справа сеть с источником [math]\ s[/math] , стоком [math]\ t[/math] , пропускными способностями рёбер [math]\ e_1[/math] , [math]\ e_2[/math] и [math]\ e_3[/math] соответственно [math]\ 1[/math] , [math]r=\dfrac-1>[/math] и [math]\ 1[/math] и пропускной способностью всех остальных рёбер, равной целому числу [math]M \geqslant 2[/math] . Константа [math]\ r[/math] выбрана так, что [math]\ r^2 = 1 — r[/math] . Мы используем пути из остаточного графа, приведённые в таблице, причём [math]\ p_1 = \< s, v_4, v_3, v_2, v_1, t \>[/math] , [math]\ p_2 = \< s, v_2, v_3, v_4, t \>[/math] и [math]\ p_3 = \< s, v_1, v_2, v_3, t \>[/math] .
| Шаг | Найденный путь | Добавленный поток | Остаточные пропускные способности | ||
|---|---|---|---|---|---|
| [math]e_1[/math] | [math]e_2[/math] | [math]e_3[/math] | |||
| [math]0[/math] | [math]-[/math] | [math]-[/math] | [math]r^0=1[/math] | [math]r[/math] | [math]1[/math] |
| [math]1[/math] | [math]\< s, v_2, v_3, t \>[/math] | [math]1[/math] | [math]r^0[/math] | [math]r^1[/math] | [math]0[/math] |
| [math]2[/math] | [math]p_1[/math] | [math]r^1[/math] | [math]r^2[/math] | [math]0[/math] | [math]r^1[/math] |
| [math]3[/math] | [math]p_2[/math] | [math]r^1[/math] | [math]r^2[/math] | [math]r^1[/math] | [math]0[/math] |
| [math]4[/math] | [math]p_1[/math] | [math]r^2[/math] | [math]0[/math] | [math]r^3[/math] | [math]r^2[/math] |
| [math]5[/math] | [math]p_3[/math] | [math]r^2[/math] | [math]r^2[/math] | [math]r^3[/math] | [math]0[/math] |
Заметим, что после шага [math]1[/math] , как и после шага [math]5[/math] , остаточные способности рёбер [math]e_1[/math] , [math]e_2[/math] и [math]e_3[/math] имеют форму [math]r^n[/math] , [math]r^[/math] и [math]0[/math] , соответственно, для какого-то натурального [math]n[/math] . Это значит, что мы можем использовать увеличивающие пути [math]p_1[/math] , [math]p_2[/math] , [math]p_1[/math] и [math]p_3[/math] бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага [math]5[/math] равен [math]1 + 2(r^1 + r^2)[/math] . За бесконечное время полный поток сойдётся к [math]\textstyle 1 + 2\sum\limits_^\infty r^i = 3 + 2r[/math] , тогда как максимальный поток равен [math]2M + 1[/math] . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.
Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину
При использовании поиска в ширину алгоритму потребуется всего лишь два шага. Дана сеть (Рис. 2).
Максимальный поток
Потоком в ориентированном графе называется отображение F из множества его рёбер в какое-нибудь числовое множество такое, что для любой вершины v верно следующее: сумма F от всевозможных рёбер с концом v равна сумме F от всевозможных рёбер с началом v .
Традиционно значения отображения F называются токами, а определение потока, грубо говоря, звучит как «в каждой вершине сумма входящих токов равна сумме исходящих». Типичный пример потока — токи в электрической цепи.
Некоторые комбинаторные задачи о распределении ресурсов (типичный пример: задача о максимальном паросочетании) сводятся к так называемой задаче о максимальном потоке. Постановка её следующая:
- на каждом ребре графа задаётся пропускная способность — действительное неотрицательное число
- в граф добавляется ребро E без пропускной способности; его начало называется стоком, а конец — источником
- рассматриваются только потоки с действительными неотрицательными токами, не превосходящими пропускные способности соответствующих рёбер
- требуется найти поток, максимизирующий ток на ребре E
Часто ребро E вообще исключают из разговора, говоря вместо «ток на E » просто «ток от источника до стока». В таком случае сумма выходящих из источника токов должна быть на этот самый ток больше суммы входящих в него токов. На этот же ток сумма входящих в сток токов должна быть больше суммы токов, выходящих из него.
Паросочетание как поток
Напомним, что паросочетанием называется набор непересекающихся рёбер в двудольном графе (говоря двудольный мы имеем в виду актуально двудольный — в котором вершины уже поделены на два класса, а рёбра бывают только вида «из одного класса в другой»).
Почти всегда на практике одной долей такого графа служит некоторый набор множеств, второй долей — объединение этих множеств, а рёбрами — принадлежности элементов множествам.
Если в двудольный граф добавить вершины A и B , из A пустить по одному ребру в каждую вершину первой доли, из каждой вершины второй доли пустить ребро в B , а затем каждому ребру назначить пропускную способность 1, то целочисленный поток от A до B в таком графе эквивалентен паросочетанию в исходном графе.
Переформулировка задачи
Решать задачу о максимальном потоке в том виде, в котором она поставлена, неудобно. Преобразуем её следующим образом: для каждой пары вершин исходного графа все рёбра, их соединяющие, объеденим в одно (произвольного направления) с нижним и верхним ограничениями на ток по нему (эти два ограничения — суммы пропускных способностей в двух возможных направлениях).
Поток в таком графе нетрудно преобразовать в поток в исходном, причём такое преобразование определено не однозначно, в отличие от «обратного». Как мы увидим позже, избавление от этой неоднозначности очень сильно упрощает задачу о максимальном потоке.
Алгоритм Форда-Фалкерсона
Перед тем как изложить алгоритм решения, договоримся об одном незначительном, но удобном упрощении: будем считать, что все токи и все пропускные способности целые. После того, как алгоритм будет изложен для целочисленных потоков, мы сделаем отдельное замечание о том, как действовать в нецелочисленном случае.
Алгоритм Форда-Фалкерсона заключается в построении последовательности потоков такой, что в каждом потоке этой последовательности (кроме начального) ток от источника к стоку строго больше, чем в предыдущем.
Начальный поток — нулевой.
Имея поток, следующий строится так: ищется простой (т.е. проходящий по каждому ребру не более одного раза) путь от источника к стоку в остаточном графе. Остаточный граф определён так: ребро от вершины a до вершины b есть тогда и только тогда, когда ток от a до b хотя бы на единицу меньше пропускной способности в соответствующую сторону. Например, если рассмотреть граф из одного ребра от a до b с ограничениями тока -1 и 1, то остаточный граф устроен так:
- если по ребру идёт ток -1, в остаточном есть только ребро от a до b
- если по ребру идёт ток 1, в остаточном есть только ребро от b до a
- если по ребру идёт ток 0, в остаточном графе есть рёбра как от a до b , так и от b до a
Если путей от источника до стока в остаточном графе нет, то алгоритм завершается. Если же такой путь есть, то токи вдоль него увеличиваются на единицу.
Алгоритм Форда-Фалкерсона не постулирует конкретный способ поиска пути в остаточном графе. Например, если такой поиск происходит «в ширину», то результирующий алгоритм носит имена Эдмондса и Карпа.
В качестве оптимизации можно на каждом шаге увеличивать ток не на единицу, а на минимальную ненулевую разницу между токами потока и соответствующими пропускными способностями рёбер. Заодно такой метод действует и для нецелочисленных потоков (с одной оговоркой — можно подобрать нецелые пропускные способности, приводящие к бесконечной последовательности потоков).
Почему оно работает?
Собственно, нужно доказать, что последний поток в последовательности даёт максимально возможный ток от источника до стока.
Самая главная хитрость доказательства — взглянуть на правильный набор рёбер. Например, подойдёт такой: один конец — вершина из множества тех, до которых можно дойти от источника по рёбрам остаточного графа; другой конец — вершина не из этого множества. Все такие рёбра обладают следующим свойством: на каждом достигнута максимальная пропускная способность, причём в направлении «от источника» (это напрямую следует из определения остаточного графа).
Осталось заметить два факта (оба следуют из определения потока):
- ток от источника к стоку равен суммарной пропускной способности рассмотренных нами рёбер
- ток от источника к стоку не может превосходить эту самую суммарную пропускную способность
Значит, мы нашли поток с максимально возможным током от источника к стоку.
Практическая реализация
В главе про обходы графов мы рассматривали вариант поиска в глубину, строящий путь (а не границу множества обработанных вершин):
std::set component(Graph &g, int v) < std::vectorpath; std::set visited<>; while (path.size() > 0) < int current_vertex = path.back(); visited.insert(current_vertex); bool found_new = false; auto n = neighbors(g,current_vertex); for (int i : n) < if (visited.count(i) == 0) < path.push_back(i); found_new = true; break; >> if (found_new) < continue; >path.pop_back(); > return visited; > Для нужд алгоритма Форда-Фалкерсона он неплохо подходит, но его нужно модифицировать для работы с остаточным графом.
Сначала модифицируем сам тип «граф»:
using Vertex = int; using Capacity = int; using Graph = std::map>; void addEdge(Graph &g, Vertex i, Vertex j, Capacity c) < g[i][j] += c; g[j][i]; // помечаем, что i -- сосед j >using Current = int; using Flow = std::map>; std::set neighbors(Graph &g, Flow &f, int v) < std::setres; for (auto x : g[v]) < // договоримся хранить ток на ребре (a,b) сразу в // двух рёбрах так, чтобы: f[a][b] == -f[a][b] auto current = f[v][x.first]; if (current < x.second) < res.insert(x.first); >> return res; > На а теперь — поиск пути в остаточном графе:
std::vector find_residual_path(Graph &g, Flow &f, Vertex src, Vertex dst) < std::vectorpath; std::set visited<>; while (path.size() > 0) < Vertex current_vertex = path.back(); // главное -- вовремя остановиться if (current_vertex == dst) < break; >visited.insert(current_vertex); bool found_new = false; auto n = neighbors(g,f,current_vertex); for (Vertex i : n) < if (visited.count(i) == 0) < path.push_back(i); found_new = true; break; >> if (found_new) < continue; >path.pop_back(); > return path; // теперь возвращаем путь, а не связную компоненту > Ну и, наконец, Форд-Фалкерсон:
Flow find_max_flow(Graph &g, Vertex src, Vertex dst) < Flow f; for (;;) < auto path = find_residual_path(g, f, src, dst); if (path.size() == 0) < break; >for (size_t i = 1; i < path.size(); i++) < Vertex u = path[i-1]; Vertex v = path[i]; f[u][v] += 1; f[v][u] -= 1; >> return f; > Поиск Максимального Потока
Максимальным поток является поток по транспортной сети, сумма потоков из истока или в сток максимальная.
Как использовать
- Выбрать Алгоритмы → Поиск максимального потока .
- Выбрать вершину истока.
- Выбрать вершину стока.
Над каждой дугой отобразится реальный поток через дугу / вес дуги. Алгоритм рассчитывает один из возможных максимальных потоков, так как таких потоков может быть несколько.
Алгоритм
Для расчёта Максимального потока мы используем алгоритм Алгоритм проталкивания предпотока.
© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)