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