Этап 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.Найдите два различных максимальных потока в транспортной сети. Решить задачу симплекс-методом и методом Форда–Фалкерсона .