Этап 1. Расстановка меток
Все вершины получают статус непомеченных.
Процедура расстановки меток.
Возьмем произвольный помеченный, но не просмотренный узел x. Пусть он имеет пометку [i, +, e(x)], где i – вершина из которой был помечен x; флаг, показывающий, что дуга (i,x) согласованна; e – величина потока, который можно пропустить по этой дуге.
Рассмотрим все непомеченные смежные вершины y, такие что дуга (x, y) согласованна. Пометим вершину y меткой [x, +, e(y)], где e(y) = min{e(x) , c(x, y) – f(x, y)}. Затем рассмотрим все непомеченные смежные вершины y, соединенные с ней несогласованной дугой. Пометим их меткой [x, -, e(y)], где e(y) = min{e(x), f(y,x)}. Теперь все рассмотренные узлы y имеют статус помеченных, а узел x - просмотренный.
Эта общая для всех узлов сети процедура. Пометим источник меткой [~, ~, ∞] и будем последовательно вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только процедура будет вызвана для стока, будет получена увеличивающая цепь и следует перейти ко второму этапу. В противном случае процедура будет вызываться, пока все помеченные вершины не станут просмотренными, и если сток сети не был достигнут – увеличивающая цепь не может быть построена и по теореме Форда-Фалкерсона имеющийся поток сети является максимальным.
Этап 2. Изменение потока.
Процедура изменения потока дуги.
Возьмем узел x. Если он имеет метку [y, +, e], то увеличим поток по дуге (y, x) на e. Если он имеет метку [y, -, e], то уменьшим поток по дуге (y, x) на e. Если y не является источником, то вызовем процедуру для узла y.
Эта процедура, будучи вызвана для стока сети, позволяет пройти по найденной увеличивающей цепи к стоку, изменяя поток на ее дугах.
Следует особо отметить, что узлы, имеющие статус “помеченных”, больше не участвуют в процессе поиска увеличивающей цепи, весьма эффективно с вычислительной точки зрения.
Алгоритм Форда-Фалкерсона гарантирует нахождение максимального потока только в сетях с целочисленными пропускными способностями. На практике “чистый” алгоритм Форда-Фалкерсона не применяется, т.к. оценка его производительности зависит от величины пропускных способностей дуг сети. Все дело в том, что в нем не дается каких либо правил выбора увеличивающей цепи.
Пример 4. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок). Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока.
Источник – вершина 1, сток – вершина 8.
Рис.5. Исходные данные к задаче о максимальном потоке
Решение: С помощью алгоритма Форда-Фалкерсона найдем наибольший поток из 1 в 8.
Шаг 1. Выбираем произвольный поток, например, 1-3-6-7-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 6. Уменьшаем пропускные способности дуг этого потока на 6, насыщенную дугу 3-6 вычеркиваем.
Шаг 2. Выбираем произвольный поток, например, 1-4-5-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 24. Уменьшаем пропускные способности дуг этого потока на 24, насыщенную дугу 4-5 вычеркиваем.
Шаг 3. Выбираем произвольный поток, например, 1-5-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 57. Уменьшаем пропускные способности дуг этого потока на 57, насыщенную дугу 1-5 вычеркиваем.
Шаг 4. Выбираем произвольный поток, например, 1-2-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 16. Уменьшаем пропускные способности дуг этого потока на 16, насыщенную дугу 2-8 вычеркиваем.
Шаг 5. Выбираем произвольный поток, например, 1-2-5-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 13. Уменьшаем пропускные способности дуг этого потока на 13, насыщенную дугу 5-8 вычеркиваем.
Шаг 6. Выбираем произвольный поток, например, 1-2-5-7-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 3. Уменьшаем пропускные способности дуг этого потока на 3, насыщенную дугу 1-2 вычеркиваем.
Шаг 7. Выбираем произвольный поток, например, 1-4-6-7-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 1. Уменьшаем пропускные способности дуг этого потока на 1, насыщенную дугу 6-7 вычеркиваем.
Шаг 8. Выбираем произвольный поток, например, 1-4-6-5-7-8. Его пропускная способность равна минимальной из всех пропускных способностей входящих в него дуг, то есть 8. Уменьшаем пропускные способности дуг этого потока на 8, насыщенную дугу 4-6 вычеркиваем. Больше путей нет. Суммарный поток 6+24+57+16+13+3+1+8=128
Рис.6. К решению задачи о максимальном потоке
Начинаем расстановку пометок.
Начальная вершина (источник) 1 имеет пометку 0.
Из этой вершины в вершины 3 и 4 ведут ненасыщенные дуги (см. рисунок 7), поэтому присваиваем им пометки соответственно, +3 и +4.
Больше пометки расставить нельзя. Значит, максимальный поток найден, причем A = {2,5,6,7,8} (непомеченные вершины) образует разрез. Величина разреза 6+9+24+57+32=128.
Рис.7. К решению задачи о максимальном потоке
Задание 1. Найти кратчайший путь из пункта a в пункт b , используя алгоритм Дейкстры.
Задание 2. Найти кратчайший путь от вершины 0 до всех вершин, используя алгоритм Дейкстры.
Задание 3.Найдите максимальный поток в сети методом Форда–Фалкерсона.
Задание 4.Найдите два различных максимальных потока в транспортной сети. Решить задачу симплекс-методом и методом Форда–Фалкерсона .