Реализация метод форда фалкерсона

Добавил пользователь Дмитрий К.
Обновлено: 04.10.2024

Алгоритм Форда-Фалкерсона

Алгоритм последовательно улучшает допустимый поток, находя так называемый дополняющий путь и увеличивая поток вдоль этого пути. Варианты алгоритма отличаются способом нахождения дополняющего пути.

В исходном алгоритме Форда–Фалкерсона способ выбора дополняющего пути не уточнялся.
В алгоритме Эдмондса-Карпа выбирается кратчайший дополняющий путь, для чего используется поиск в ширину на каждой итерации;
В алгоритме Диница для выбора кратчайшего пути поддерживается «расслоение» графа, так что поиск в ширину выполняется значительно реже.

1.2 Математическое описание алгоритма

Математическая постановка задачи приведена в статье «Поиск максимального потока в транспортной сети», там же введены используемые обозначения.

Пусть задан некоторый допустимый поток [math]f[/math] . Дополняющим путём называется последовательность рёбер [math]e_0 = (s, v_1), e_1 = (v_1, v_2), \ldots, e_k = (v_k, t)[/math] , каждое из которых обладает положительной остаточной пропускной способностью [math]c_f(e_i) = c(e_i) - f(e_i) \gt 0[/math] .

Поток останется допустимым, если увеличить его вдоль дополняющего пути на число [math]\delta = \min \ < c(e_i) - f(e_i) \>\gt 0[/math] , при этом величина потока возрастёт на то же число [math]\delta[/math] . Для сохранения антисимметричности увеличение потока производится присваиваниями

[math] f(e_i) \leftarrow f(e_i) + \delta, \quad f(e_i^R) \leftarrow f(e_i^R) - \delta, \quad i = \overline<0, k>. [/math]

Если дополняющего пути не существует, то поток [math]f[/math] является максимальным.

1.3 Вычислительное ядро алгоритма

Вычислительными ядрами, на которые приходится наибольший объём вычислений, являются:

увеличение потока вдоль дополняющего пути.

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

В алгоритме Эдмондса–Карпа выполняются следующие операции:

поиск в ширину и определение кратчайшего пути на каждой итерации, сложность [math]O(m + n)[/math] , общая сложность [math]O(m^2n)[/math] ;
обновление потока вдоль дополняющего пути, сложность [math]O(n)[/math] , общая сложность [math]O(n^2 m)[/math] .

Таким образом, общая сложность составляет [math]O(m^2n)[/math] .

В алгоритме Диница выполняются следующие операции:

поиск кратчайшего пути и обновление потока вдоль дополняющего пути на каждой итерации, сложность [math]O(n)[/math] , общая сложность [math]O(mn^2)[/math] ;
обновление расслоения на каждой итерации, сложность [math]O(1)[/math] , общая сложность [math]O(mn)[/math] ;
поиск в ширину для построения нового расслоения, сложность [math]O(m)[/math] , число построений не более [math]n[/math] , общая сложность [math]O(mn)[/math] .

Таким образом, общая сложность составляет [math]O(mn^2)[/math] .

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

Основной объём вычислений в алгоритме Форда-Фалкерсона приходится на поиск путей от источника к стоку. С этой целью может применяться поиск в ширину, который хорошо распараллеливается. Наилучших результатов можно достичь, если распределить вершины между узлами по слоям примерно одинаковой толщины, так что в каждом слое вершины были бы примерно на одинаковом удалении от источника (такое расслоение также можно найти поиском в ширину).

Реализация метод форда фалкерсона

Алгоритмы
обхода графа

Алгоритмы поиска
кратчайшего пути

Нахождения наименьшего
остового дерева

Максимальные потоки
и паросочетания

Алгоритм Форда-Фалкерсона

Алгоритм Форда-Фалкерсона — решает задачу нахождения максимального потока в транспортной сети.

Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его еще можно доставить от истока к стоку при данных пропускных способностях труб.

Ключевую роль в методе Форда-Фалкерсона играют два понятия: остаточные сети и дополняющие пути. Пусть дана сеть и поток в ней. Тогда остаточная сеть состоит из тех ребер (называемых также остаточными), поток по которым можно увеличить. Заметим, что остаточное ребро не обязано быть ребром исходной сети. Такие "странные" ребра появляются когда имеется поток вещества в обратном направлении — ведь этот поток можно уменьшить. Назовем дополняющим путем простой путь из истока в сток в остаточной сети. Из определения остаточной сети вытекает, что по всем ребрам дополняющего пути можно переслать ещё сколько-то вещества, не превысив их пропускную способность. Величину наибольшего потока, который можно переслать по дополняющему пути назовем остаточной пропускной способностью пути. Очевидно, она равна значению минимального остаточного ребра, входящего в данный путь.

При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р, и поток f вдоль каждого ребра данного пути увеличивается на величину остаточной пропускной способности с_f (р). Реализация данного метода вычисляет максимальный поток в графе G = (V, Е) путем обновления потока f[u,v] между каждой парой вершин и и v, соединенных ребром. Если вершины u и v не связаны ребром ни в одном направлении, неявно предполагается, что f[u, v] = 0. Предполагается, что значения пропускных способностей задаются вместе с графом и с (u, v) = 0, если (u, v) є Е.
Остаточная пропускная способность с_f (u, v) вычисляется по формуле c_f (u, v) = с (u, v) - f (u, v).

Формальное описание [вверх]

Строки 1-3 инициализируют поток f значением 0. В цикле while в строках 4-8 выполняется неоднократный поиск увеличивающего пути р в G_f, и поток f вдоль пути р увеличивается на остаточную пропускную способность C_f (р). Когда увеличивающих путей больше нет, поток f является максимальным.

Оценка сложности [вверх]

Время выполнения процедуры Ford_Fulkerson зависит от того, как именно выполняется поиск увеличивающего пути р в строке 4. При неудачном методе поиска алгоритм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно сходится к максимальному значению потока.

Выполнение строк 1-3 занимает время в (Е). Цикл while в строках 4-8 выполняется не более |f*| раз, поскольку величина потока за каждую итерацию увеличивается по крайней мере на одну единицу. Время поиска пути в остаточной сети составляет О (V + Е') = О (Е), если используется поиск в глубину или поиск в ширину. Каждая итерация цикла while занимает время О (Е), так что в результате общее время выполнения составляет О(Е|f*|), где f* — максимальный поток, найденный данным алгоритмом.

Алгоритм Форда-Фалкерсона

Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.

При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.

Постановка задачи

Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.

Исходный граф

Как работает сам алгоритм?

Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:

Отправлять определенное количество потока из текущей вершины в соседние.

Возвращать определенное количество потока из соседних вершин в текущую.

В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.

Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.

Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.

Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.

Возвращаемся обратно к нахождению пути в остаточной сети после модификации.

Разбор конкретного примера

Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.

Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.

Сколько потока можем провести по этому пути.
- Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:

Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.

Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .

Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:

Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:

На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:

Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

На 4-ой итерации находим следующий путь в остаточной сети:

Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Итоговая остаточная сеть

На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.

Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!

Алгоритм Форда-Фалкерсона

История создания алгоритма Форда-Фалкерсона, краткое описание его алгоритма, особенности работы, анализ сложности. Создание распараллеленного варианта алгоритма и его краткое описание. Основные характеристики теории графов, специфика, пути и маршруты.

Рубрика	Программирование, компьютеры и кибернетика
Вид	контрольная работа
Язык	русский
Дата добавления	06.08.2013
Размер файла	246,3 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

алгоритм форд фалкерсон граф

Пояснительная записка к курсовой работе: с., рис., табл., разделов, приложения.

АЛГОРИТМ, ГРАФ, РЕБРО, ВЕРШИНА, МАКСИМАЛЬНЫЙ ПОТОК, ПАРАЛЛЕЛЬНЫЙ, ПСЕВДОКОД, БЛОКСХЕМА, РЕАЛИЗАЦИЯ

Объект исследования: алгоритм Форда-Фалкерсона

Цель работы: закрепление знаний и умений, полученных в процессе теоретического обучения.

Метод работы: закрепление теоретических знаний с помощью разработки программы, реализующий данный алгоритм.

Объектом исследования курсовой работы стала реализация алгоритма Форда-Фалкерсона.

Целями работы являлись:

1) ознакомление с алгоритмом Форда-Фалкерсона, его историей;

2) реализация алгоритма, для построения нахождения максимального потока сети;

3) анализ трудоёмкости алгоритма;

4) тестирование алгоритма.

В теории графов транспортная сеть -- ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток. Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из источника в сток. Транспортная сеть может быть использована для моделирования, например, дорожного трафика. Целочисленная транспортная сеть -- транспортная сеть, все пропускные способности ребер которой -- целые числа.

Поток -- функция со следующими свойствами для любых вершин:

1) Ограничение пропускной способности;

2) Поток не может превысить пропускную способность;

3) Поток из вершины в другую должен быть противоположным в другом направлении;

4) Сохранение потока. для всех , кроме источника и стока.

Первый отчет «Максимальный поток в сети» датируется 19 ноября 1954 года. Авторы отчета - Форд и Фалкерсон, доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Пропускной способностью разреза называется сумма пропускных способностей ребер, концы которых лежат в разных классах.) В 1955 году в работе Робахера было упомянуто, что впервые эту теорему доказал Фалкерсон.

Граф можно задавать несколькими путями, однако самый просто способ задания - задание графа матрицей смежности. Тем не менее, этот способ подходит исключительно для таких сетей, которые имеют начальную пропускную способностью равную длине ребра.

Алгоритм широко применяется в сфере перевозок, для того чтобы найти оптимальные маршруты перевозки грузов. Также широкое применение он находит в компьютерных технологиях, коммуникационных сетях, электрических сетях.

Суть распараллеливания алгоритма заключается в уменьшении времени работы с большими объемами входных данных. Стоит заметить, что сложность и трудоемкость алгоритма напрямую зависит от способа реализации. Пример описанных в проекте, работает при помощи алгоритма обхода графа в ширину. Этот алгоритм нужен для того, чтобы искать пути в заданном графе из источника в сток.

1. Графы

1.1 Основные характеристики графов

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины.

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Граф G (X, A)- полный, если для любой пары вершин x_iи x_j существует ребро (x_i, x_j).

1.2 Пути и маршруты

Маршрутом или цепью в неориентированном графе G называется такая последовательность (конечная или бесконечная) ребер a₁, a₂. a_n,…, что каждые соседние два ребра a_i и a_i+₁имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a₁,a₂. a_n) имеется первое ребро a₁и последнее ребро a_n. Вершина x₁, инцидентная ребру a₁, но не инцидентная ребру a₂, называется началом маршрута, а вершина x_n, инцидентная ребру a_n, но не инцидентная ребру a_n-₁, называется концом маршрута.

Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут.

Замкнутый маршрут называется циклом. Маршрут (цикл), в котором все ребра различны, называется простым маршрутом или простой цепью (циклом). Маршрут (цикл), в котором все вершины, (кроме первой и последней), различны, называется элементарным маршрутом или элементарной цепью (циклом).

Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути.

Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.

Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.

Иногда дугам графа сопоставляются числа называемые весом, или длиной дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.

2. Алгоритм Форда-Фалкерсона

2.1 Краткое описание алгоритма

Идея алгоритма заключается в следующем. Выбираем такой путь от источника с к стоку, чтобы для каждого ребра остаточная пропускная способность была строго больше нуля. При этом ребра на данном пути могут проходиться как в прямом, так и в обратном направлении. Выбираем минимальное значение среди остаточных пропускных способностей ребер данного пути. Увеличиваем поток на каждом из ребер данного пути на выбранное минимальное значение. Далее ищем следующий аналогичный путь.

Работа алгоритма продолжается до тех пор, пока удается находить данные пути.

Сразу отметим, что данный алгоритм относится к классу недетерминированных, т.е. каждый следующий шаг алгоритма определен неоднозначно. И время работы (количество шагов) алгоритма зависит от того, как будут выбираться шаги.

Неформальное описание алгоритма:

ѕ Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью;

ѕ В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся;

ѕ Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток;

ѕ На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью ;

ѕ Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему -- уменьшаем на ;

ѕ Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;

ѕ Возвращаемся на шаг 2.

Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению. На рисунке 1 представлена общая схема работы программы.

Более формально, мы имеем ориентированный граф G = (V; E), со множеством вершин V и множеством ребер E. Во множестве V выделены две вершины: s - источник и t - сток. При этом, у вершины s есть только ходящие ребра, у вершины t есть только входящие ребра.

Если ребро имеет максимальную пропускную способность x и потокy, то остаточной пропускной способностью ребра называется число xy. Смысл остаточной пропускной способности заключается в том, на сколько еще можно увеличить поток на данном ребре.

Следующим этапом выполнения программы является нахождение маршрутов в графе. Поиск маршрутов реализуется с помощью алгоритма обхода графа в ширину. На рисунке 2 представлена блок-схема алгоритма обхода графа в ширину.

Алгоритм Форда-Фалекрсона работает пока можно найти хотя бы один путь из источника в сток, итеративно увеличивая поток на минимальную величину. На рисунке 3 представлена блок-схема алгоритма Форда-Фалкерсона.

Рисунок 1 - Общая схема

Рисунок 2 - Блок-схема алгоритма поиска в ширину

Рисунок 3 - Алгоритм Форда-Фалкерсона

2.2 Анализ сложности алгоритма

На каждом шаге алгоритм добавляет поток увеличивающего пути к уже имеющемуся потоку. Если пропускные способности всех рёбер -- целые числа, легко доказать по индукции, что и потоки через все рёбра всегда будут целыми. Следовательно, на каждом шаге алгоритм увеличивает поток, по крайней мере, на единицу, следовательно, он сойдётся не более чем за O(f) шагов, где f -- максимальный поток в графе. Можно выполнить каждый шаг за время O(E), где E -- число рёбер в графе, тогда общее время работы алгоритма ограничено O(Ef).

Если величина пропускной способности хотя бы одного из рёбер -- иррациональное число, то алгоритм может работать бесконечно, даже не обязательно сходясь к правильному решению. На рисунке 4 представлен псевдокод алгоритма Форда-Фалкерсона.

2.3 Псевдокод

Ford_Fulkerson(G, s, t)

1 for каждого ребра (u, v) є E[G]

4 while существует путь p из s в t в остаточной сети G_f

5 do сf(р) «-- min f(u, v) : (u, v) принадлежит р>

6 for каждого ребра (u, v) in p

Рисунок 4 - Псевдокод алгоритма Форда-Фалкерсона

3. Распараллеленный вариант алгоритма

3.1 Библиотека omp.h

Разработчики OpenMP хотели предоставить простой способ создания потоков в приложениях, не требуя от программиста знаний о создании, синхронизации и уничтожении потоков, а также необходимости определения, сколько потоков следует создать. Для этого разработчики OpenMP создали независимый от платформы набор прагм, директив, вызовов функций и переменных среды, которые явным образом указывают компилятору, как и где именно следует вставить потоки в приложение. Большинство циклов можно распараллелить, вставив всего одну прагму непосредственно перед циклом. Более того, оставив исполнение рутинных функций компилятору и OpenMP, вы можете больше времени уделить определению того, какие циклы следует распараллелить, и как наилучшим образом изменить структуру алгоритмов для достижения максимальной производительности. Максимальная производительность OpenMP реализуется при использовании этого инструмента для распараллеливания "горячих точек", - наиболее трудоемких циклов в приложении.

Написание параллельного варианта сводится к написанию прагм. Прагмы - это директивы препроцессора, игнорируемые компиляторами, которые не поддерживают данную технологию. То есть программа, написанная с применением данной технологии, могут быть скомпилированы как последовательные, при том среда разработки не выдаст никакой ошибки. Список директив, использованных в данной работе:

Так как потоки выполняют свои операции параллельно, то заканчивать свою работу будут в разное время, поэтому данный вариант распараллеливания будет бесполезен при использовании на задачах класса P = NP.

3.2 Краткое описание распараллеливания алгоритма

При распараллеливании используется библиотека omp.h, использующая инструменты OpenMP технологии. Алгоритм делится на несколько потоков, и на каждом из потоков выполняется своя часть программы. Параллелизм реализуется за счет написания прагм в соответствующих фрагментах кода. На рисунке 5 представлен фрагмент кода, с использованием нижеописанных прагм. Полный листинг представлен в приложении Б.

Основной целью распараллеливания был анализ ускорения работы алгоритма. На практике, ускорение заметно только на очень больших наборах данных, но совсем незначительное. Ожидаемое ускорение, вычисленное по формуле Амдаля, при 25% операций выполненных параллельно на 2 процессорах составляет 300% от последовательного выполнения, однако на практике такого ускорения достигнуто не было, в виду целого ряда факторов, влияющих на быстроту выполнения операций.

Рисунок 5 - Фрагмент распараллеленного кода программы

Заключение

алгоритм форд фалкерсон граф

В процессе создания данного проекта была рассмотрена теория графов в общем, изучены понятия путей и маршрутов. Разработана программа, реализующая алгоритм Форда-Фалкерсона в MicrosoftVisualStudio 2010.Алгоритм может найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины - роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.

Также были углублены знания, полученные в процессе выполнения лабораторных работ по предмету «Программирование».

Список использованных источников

1. ГОСТ 7.32-2001. Отчёт о научно-исследовательской работе. Структура и правила оформления [Текст]. - Взамен ГОСТ 7.32-91 ;введ. 2001-07-01. - Минск :Межгос. совет по стандартизации, метрологии и сертификации ; М. : Изд-во стандартов, 2001. - 16 с. - (Система стандартов по информации, библиотечному и издательскому делу).

3. Канева, Ольга Николаевна. Дискретная математика [Текст] : учеб.пособие / О.Н. Канева, 2009. - 87 с.

4. Левин, А. Самоучитель работы на компьютере в вопросах и ответах[Текст]: учеб. пособие / А. Левин -М.: «Аквариум», 2007г. - 644с.

Реализация метод форда фалкерсона

На этом шаге рассмотрим пример применения метода Форда-Фалкерсона для решения задачи о максимальном потоке.

Метод Форда-Фалкерсона назван методом, а не алгоритмом, т.к. он допускает несколько реализаций с различным временем выполнения.

Метод Форда-Фалкерсона базируется на трех идеях, которые используются во многих потоковых алгоритмах и задачах: остаточные сети, увеличивающие пути и разрезы.

Метод Форда-Фалкерсона итеративно увеличивает значение потока. Вначале поток обнуляется: f(u, v) = 0 для всех u, v ∈ V . На каждой итерации величина потоки в G увеличивается посредством поиска "увеличивающего пути" в связанной "остаточной сети" G_f . Зная ребра увеличивающего пути в G_f , мы можем идентифицировать конкретные ребра в G , для которых можно изменить поток таким образом, что его величина увеличится.

Каждая итерация метода Форда-Фалкерсона увеличивает величину потока, но как будет видно далее, поток через конкретное ребро G может возрастать или уменьшаться; уменьшение потока через некоторые ребра может быть необходимым для того, чтобы позволить алгоритму переслать больший поток от истока к стоку. Мы многократно увеличивам поток до тех пор, пока остаточная сеть не будет иметь ни одного увеличивающего пути.

Метод Форда-Фалкерсона можно задать следующей функцией:

Ford-Fulkerson-Method(G, s, t)
1 Инициализация потока f нулевым значением
2 while существует увеличивающий путь p в остаточной сети G_f
3 увеличиваем поток f вдоль пути p
4 return f

В процедуре используются следующие обозначения:

Транспортная сеть G = (V, E) представляет собой ориентированный граф, в котором каждое ребро (u, v) ∈ E имеет неотрицательную пропускную способность c(u, v) ≥ 0
Две вершины транспортной сети s - исток и t - сток.

На следующем шаге рассмотрим понятие остаточной сети в методе Форда-Фалкерсона.

Реализация метод форда фалкерсона

Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда—Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
— исток сети; — сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.

r[0,1] = 39; r[4,7] = 44; r[6,3] = 33; r[5,7] = 53; r[0,2] = 10;
r[4,2] = 18; r[6,7] = 95; r[5,4] = 16; r[0,3] = 23; r[2,5] = 61;
r[2,1] = 81; r[6,5] = 71; r[1,4] = 25; r[2,6] = 15; r[3,2] = 20

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток — это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.

4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.

5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.

6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.

2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки ( красные круги)

Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы — в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети
Вычисление величины максимального потока

Метод Форда-Фалкерсона

Теорема Форда и Фалкерсона о связи минимального потока и максимального разреза позволяет обосновать следующий общий метод решения задачи о максимальном потоке. Идея состоит в том, что произвольный поток в сети можно дополнить до максимального. По произвольному потоку f рассмотрим «остаточную сеть» этого потока. Ребрами сети будут исходные ребра графа с пропускной способностью cf(uv) = c(uv) – f(uv), а также обратные ребра с пропускной способностью cf(uv) = f(vu). Метод Форда и Фалкерсона состоит в нахождении в остаточной сети произвольного пути из источника в сток, и дополнении существующего потока (изначально нулевого) вдоль этого пути. Теорема о максимальном потоке и минимальном разрезе позволяет обосновать тот факт, что в случае если такого пути не существует, то поток является максимальным.

В оригинале этот метод был сформулирован в 1956 без использования «остаточной сети», однако его описание в терминах обычной сети очень громоздко, поэтому мы его здесь не приводим. Термин «остаточная сеть» появился позднее, и в настоящее время является одним из основных инструментов исследователей в области потоков.

Алгоритм Эдмондса-Карпа

Однако, в общем случае метод Форда и Фалкерсона не является корректным. Существует пример сети с иррациональными пропускными способностями, для которой алгоритм Форда и Фалкерсона не остановится (будет работать «бесконечное время»). Для сетей с целочисленными пропускными способностями время работы составляется O(UVE), где U – максимальная пропускная способность, V – количество вершин и E количество ребер в сети. Сети с рациональными пропускными способностями могут быть сведены к целочисленному случаю путем домножения на наибольший общий делитель знаменателей всех дробей.

В 1969 году Эдмондсом и Карпом была предложена модификация этого алгоритма, позволяющая получить гарантированное время O(VE^2) работы алгоритма следующим способом: на каждом шаге путь из источника в сток нужно выбирать не произвольный, а кратчайший. В этом случае удается доказать оценку O(VE) на число фаз работы алгоритма. Искомая оценка следует из того, что в неориентированном графе возможно найти расстояние между двумя вершинами за время O(E).

Дальнейшие улучшения алгоритма построения максимального потока

В 1970 году Дициц опубликовал принципиально новый алгоритм нахождения максимального потока, основанный на поиске псевдомаксимального ("блокирующего") потока во вспомогательной сети.

Блокирующий поток – это поток, величину которого невозможно улучшить путем лишь увеличения потока вдоль отдельных ребер. Строить такой поток Диниц предлагал при помощи классического алгоритма поиска «в ширину».

Другое направление исследований – улучшенные алгоритмы для нахождения максимального потока в сети с целочисленными пропускными способностями. Метод, предложенный Эдмондсом и Карпом в 1972 году (и независимо Диницом в 1973) получил название метода масштабирования пропускных способностей (capacity scaling). Идея метода проста: поток в сети с пропускными способностями, равными половине пропускных способностей исходной сети, мы легко можем получить поток в исходной сети путем умножения его значения на 2. Отдельно нужно обрабатывать ребра с нечетными пропускными способностями. Полученный алгоритм имеет время работы O(nm log U), где n – число вершин сети, m – число ребер, U – максимальная пропускная способность.

Карзанову в 1974г удалось, с помощью модификации алгоритма Диница, добиться оценки быстродействия O(n^3). Им также впервые было введено понятие “предпотока”. В 1978г Малхотри, Кумару м Махешвари (Malhotra, Kumar, Maheshwari) удалось повторить этот результат, однако их алгоритм отличался от алгоритма Карзанова.

Лучший из известных на сегодняшний день алгоритмов был предложен в 1997 году Гольдбергом и Рао (Goldberg, Rao). В качестве вспомогательной процедуры алгоритм использует структуру данных, полученную Гольдбергом и Тарьяном (Tarjan).
В заключение приведем сводную хронологическую таблицу результатов, полученных для задачи о максимальном потоке (везде далее n – число вершин сети, m – число ребер, U – максимальная пропускная способность ребер сети)

Алгоритм Форда – Фулкерсона - Ford–Fulkerson algorithm

Метод Форда – Фулкерсона или алгоритм Форда – Фулкерсона ( FFA ) - это жадный алгоритм, который вычисляет максимальный поток в потоковой сети . Иногда его называют «методом», а не «алгоритмом», поскольку подход к поиску дополнительных путей в остаточном графе не полностью определен или определен в нескольких реализациях с разным временем выполнения. Он был опубликован в 1956 году Л. Р. Фордом-младшим и Д. Р. Фулкерсоном . Название «Форд – Фулкерсон» также часто используется для алгоритма Эдмондса – Карпа , который представляет собой полностью определенную реализацию метода Форда – Фулкерсона.

Идея алгоритма заключается в следующем: пока существует путь от источника (начальный узел) до приемника (конечный узел), с доступной емкостью на всех ребрах пути, мы отправляем поток по одному из путей. Потом находим другой путь и так далее. Путь с доступной пропускной способностью называется дополнительным путем .

Содержание

Алгоритм

Позвольте быть графом, и для каждого ребра от u до v , позвольте быть пропускной способностью и быть потоком. Мы хотим найти максимальный поток от источника s до стока t . После каждого шага в алгоритме сохраняется следующее: грамм ( V , E ) <\ Displaystyle G (V, E)>c ( ты , v ) <\ Displaystyle с (и, v)>ж ( ты , v )

Это означает, что поток через сеть является законным после каждого раунда в алгоритме. Мы определяем остаточную сеть как сеть с пропускной способностью и без потока. Обратите внимание, что может случиться так, что поток от v к u разрешен в остаточной сети, но не разрешен в исходной сети: if и then . грамм ж ( V , E ж ) <\ displaystyle G_ (V, E_ )> c ж ( ты , v ) знак равно c ( ты , v ) - ж ( ты , v ) <\ displaystyle c_ (u, v) = c (u, v) -f (u, v)> ж ( ты , v ) > 0 <\ displaystyle f (u, v)> 0>c ( v , ты ) знак равно 0 <\ displaystyle c (v, u) = 0>c ж ( v , ты ) знак равно c ( v , ты ) - ж ( v , ты ) знак равно ж ( ты , v ) > 0 <\ Displaystyle c_ (v, u) = c (v, u) -f (v, u) = f (u, v)> 0>

ж ( ты , v ) ← 0 <\ displaystyle f (u, v) \ leftarrow 0>для всех краев ( ты , v )

Хотя существует путь p от s до t in , такой, что для всех ребер : грамм ж <\ displaystyle G_ > c ж ( ты , v ) > 0 <\ displaystyle c_ (u, v)> 0> ( ты , v ) ∈ п <\ displaystyle (u, v) \ in p>

Находить c ж ( п ) знак равно мин < c ж ( ты , v ) : ( ты , v ) ∈ п ><\ Displaystyle c_ (p) = \ min \ (u, v) :( u, v) \ in p \>>

Для каждого края ( ты , v ) ∈ п <\ displaystyle (u, v) \ in p>

ж ( ты , v ) ← ж ( ты , v ) + c ж ( п ) <\ displaystyle f (u, v) \ leftarrow f (u, v) + c_ (p)> ( Отправьте поток по пути )
ж ( v , ты ) ← ж ( v , ты ) - c ж ( п ) <\ displaystyle f (v, u) \ leftarrow f (v, u) -c_ (p)> ( Поток может быть «возвращен» позже )

«←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
« return » завершает алгоритм и выводит следующее значение.

Путь на шаге 2 можно найти, например, с помощью поиска в ширину (BFS) или поиска в глубину в . Если вы используете первый, алгоритм называется Эдмондс – Карп . грамм ж ( V , E ж ) <\ displaystyle G_ (V, E_ )>

Если на шаге 2 больше нет путей, s не сможет достичь t в остаточной сети. Если S - это набор узлов, достижимых s в остаточной сети, то общая пропускная способность в исходной сети ребер от S до остальной части V равна, с одной стороны, общему потоку, который мы нашли от s до t , и с другой стороны, служит верхней границей для всех таких потоков. Это доказывает, что найденный нами поток максимален. См. Также теорему о максимальном расходе и минимальном отсечении .

Сложность

Путем добавления пути увеличения потока к потоку, уже установленному на графике, максимальный поток будет достигнут, когда на графике больше нет путей увеличения потока. Однако нет уверенности в том, что эта ситуация когда-либо будет достигнута, поэтому лучшее, что можно гарантировать, - это то, что ответ будет правильным, если алгоритм завершится. В случае, если алгоритм работает вечно, поток может даже не сходиться к максимальному потоку. Однако такая ситуация возникает только при нерациональных значениях расхода. Когда емкости являются целыми числами, время выполнения Форда – Фулкерсона ограничено (см. Большую нотацию O ), где - количество ребер в графе, а - максимальный поток в графе. Это потому, что каждый дополнительный путь может быть найден во времени и увеличивает поток, по крайней мере , на целое число с верхней границей . О ( E ж ) <\ displaystyle O (Ef)>E <\ displaystyle E>ж <\ displaystyle f>О ( E ) <\ displaystyle O (E)>1 <\ displaystyle 1>ж

Вариантом алгоритма Форда – Фулкерсона с гарантированным завершением и временем выполнения, не зависящим от максимального значения потока, является алгоритм Эдмондса – Карпа , который выполняется во времени. О ( V E 2 ) <\ displaystyle O (VE ^ <2>)>

Интегральный пример

В следующем примере показаны первые шаги Форда – Фулкерсона в потоковой сети с 4 узлами, источником и приемником . Этот пример показывает наихудшее поведение алгоритма. На каждом этапе по сети отправляется только поток . Если бы вместо этого использовался поиск в ширину, потребовалось бы всего два шага. А <\ displaystyle A>D <\ displaystyle D>1

Обратите внимание, как поток "отодвигается" от до при нахождении пути . C <\ displaystyle C>B <\ displaystyle B>А , C , B , D

Пример без завершения

Шаг	Расширение пути	Отправленный поток	Остаточные мощности
Шаг	Расширение пути	Отправленный поток	е 1 <\ displaystyle e_ <1>>	е 2 <\ displaystyle e_ <2>>	е 3 <\ displaystyle e_ <3>>
0	р 0 знак равно 1 <\ displaystyle r ^ <0>= 1>	р	1
1	< s , v 2 , v 3 , т > <\ displaystyle \ , v_ <3>, t \>>	1	р 0 <\ displaystyle r ^ <0>>	р 1 <\ displaystyle r ^ <1>>	0
2	п 1 <\ displaystyle p_ <1>>	р 1 <\ displaystyle r ^ <1>>	р 2 <\ displaystyle r ^ <2>>	0	р 1 <\ displaystyle r ^ <1>>
3	п 2 <\ displaystyle p_ <2>>	р 1 <\ displaystyle r ^ <1>>	р 2 <\ displaystyle r ^ <2>>	р 1 <\ displaystyle r ^ <1>>	0
4	п 1 <\ displaystyle p_ <1>>	р 2 <\ displaystyle r ^ <2>>	0	р 3 <\ displaystyle r ^ <3>>	р 2 <\ displaystyle r ^ <2>>
5	п 3 <\ displaystyle p_ <3>>	р 2 <\ displaystyle r ^ <2>>	р 2 <\ displaystyle r ^ <2>>	р 3 <\ displaystyle r ^ <3>>	0

Обратите внимание, что после шага 1, а также после шага 5 остаточные мощности ребер , и находятся в виде , и , соответственно, для некоторых . Это означает , что мы можем использовать расширяющий путь , , и бесконечно много раз , и оставшиеся способности этих краев всегда будут находиться в одной и ту же форме. Общий поток в сети после шага 5 составляет . Если мы продолжим использовать дополнительные пути, как указано выше, общий поток сходится к . Однако обратите внимание на то, что существует поток стоимости , отправляя единицы потока , 1 единицу потока и единицы потока . Следовательно, алгоритм никогда не завершается, и поток даже не сходится к максимальному потоку. е 1 <\ displaystyle e_ <1>> е 2 <\ displaystyle e_ <2>> е 3 <\ displaystyle e_ <3>> р п <\ Displaystyle г ^ <п>> р п + 1 <\ Displaystyle г ^ <п + 1>> 0 <\ displaystyle 0>п ∈ N <\ Displaystyle п \ в \ mathbb > п 1 <\ displaystyle p_ <1>> п 2 <\ displaystyle p_ <2>> п 1 <\ displaystyle p_ <1>> п 3 <\ displaystyle p_ <3>> 1 + 2 ( р 1 + р 2 ) <\ Displaystyle 1 + 2 (г ^ <1>+ г ^ <2>)> 1 + 2 ∑ я знак равно 1 ∞ р я знак равно 3 + 2 р <\ Displaystyle \ textstyle 1 + 2 \ сумма _ <я = 1>^ <\ infty>г ^ <я>= 3 + 2r> 2 M + 1 <\ displaystyle 2M + 1>M <\ displaystyle M>s v 1 т <\ displaystyle sv_ <1>t> s v 2 v 3 т <\ displaystyle sv_ <2>v_ <3>t> M <\ displaystyle M>s v 4 т <\ displaystyle sv_ <4>t>

Другой пример без завершения, основанный на алгоритме Евклида, приведен Backman & Huynh (2018) , где они также показывают, что в худшем случае время работы алгоритма Форда-Фулкерсона в сети в порядковых номерах равно . грамм ( V , E ) <\ Displaystyle G (V, E)>ω Θ ( | E | ) <\ Displaystyle \ omega ^ <\ Theta (| E |)>>

Максимальный поток, метод Форда-Фалкерсона и Эдмондса-Карпа

Почему веса ребер ограничены в диапазоне -99 . +99 ? И почему нет возможности поставить между двумя вершинами больше одного ребра ?

Очевидно, таковы принятые автором визуализатора ограничения.

Большое спасибо за проделанную работу! Визуализатор помог мне до конца понять алгоритм :)

Какое время работы алгоритма?

Которого из двух? В предлагаемой программе представлены 2 алгоритма: Форда-Фалкерсона и Эдмондса-Карпа. Подробности см. в описании алгоритма, а также в книге, послужившей источником для автора визуализатора.

Замучился тыкать мышкой, чтобы поставить пропускную способность с 93 (рандомно поставила программа ) до 7, а дуг у меня было 15.

есть такая кнопка сохранить/загрузить дурень

Спасибо огромное без визуализатора, ни<. > непонимал, завтра экз.Так что браво).

Успехов Вам.
Надеемся лишь, что экзамен не по русскому языку. В противном случае будут большие трудности. ;)

Если не затруднит, отпишитесь по сложности, ибо в описании алгоритма(ов) не нашел.

Спасибо большое, очень помогло.

Скажите, а есть возможность связаться с автором сего творения?

Вообще-то, это секретная информация. Но, в порядке исключения, инструктируем: в визуализаторе есть кнопочка "?". Если повезет, кликнув, найдете координаты автора "сего творения".

Просто белый экран. ( ничего не вижу.

Может быть, это толстый слой пыли? Другие версии в голову не приходят. ;)

Отличная программа, но нашёл баг: в произвольной сети допустим случай, когда в (!) источник идет единственное звено с нулевой пропускной способностью. Я ожидал, что алгоритм прервётся в самом начале, мол, нет из S подходящих дуг. Но нет - алгоритм выдаёт, что "максимальный поток равен 35" :) как так?

Согласно математической модели в источник S поступает извне бесконечный по величине поток, а не нулевой. Как Вы сумели добиться визуализации своего примера, остается загадкой.

P.S. В другой ситуации, когда из S исходили два ребра с пропускной способностью 0, алгоритм сработал корректно.

Вообще говоря, визуализатор является лишь демонстрационной моделью, не предназначенной заменить полнофункциональную вычислительную программу. Возможные ошибки на отдельных примерах неприятны, но не критичны для понимания алгоритма.

Где можно скачать программу для реализации метода Форда-Фалкерсона?

См., например, здесь. Вообще-то, поисковик легко найдет немало таких адресов.

Прикольная программа, чертовки помогла понять как решать методом Форда-Фалкерсона. Автору - большое спасибо!

Из минусов можно отметить, что, например, при 8 точках значения пропускных способностей накладываются и не видно что там написано.

Еще заметила один баг при рассмотрении своего примера. По дуге (0,2) не считает, говорит что не может.

Хотя вроде ответ выводит как надо :)

Огромное спасибо! Если бы не вы, не знаю, как бы я понял алгоритм) Формальное описание практически невозможно понять)

Дичайше вас благодарю за столь толковый визуализатор. Надеюсь, понятое здесь поможет мне на зачёте.

Читайте также: