Поиск потока минимальной стоимости

Припишем каждой дуге (x, y) графа G =(V, E) число a (x, y), равное стоимости прохождения единицы потока по дуге (x, y).

В задаче о потоке минимальной стоимости требуется переслать фиксированное число единиц потока (v) из источника (s) в сток (t) с минимальной стоимостью. То есть требуется найти

min{ å a (x, y)× f (x, y) }

(x, y)Î E

при ограничениях 7.1-7.4.

Заметим, что задачу о максимальном потоке можно рассматривать как частный случай задачи о потоке минимальной стоимости, в котором все дуговые стоимости a (x, y) равны нулю, а величина v совпадает с величиной максимального потока.

Идея алгоритма поиска потока минимальной стоимости состоит в следующем:

- вначале из вершины s в вершину t пересылается как можно больше единиц потока, полная стоимость прохождения по сети каждой из которых равна нулю (p =0);

- затем из s в t пересылается как можно больше единиц потока, полная стоимость прохождения по сети каждой из которых равна единице (p =1) и так далее;

- процесс заканчивается, когда будет передано заданное число (v) единиц потока или поток достигнет своего максимального значения.

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

Это осуществляется с помощью приписывания каждой вершине x целого числа p (x). Эти числа выбираются так, что p (s)=0; p (t)= p; 0£ p (x)£ p, (x ¹ s, x ¹ t). При этом изменение потока допускается только в тех дугах (x, y), для которых

p (y)- p (x)= a (x, y) (7.5)

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

С учетом этих соображений сформулируем алгоритм поиска потока минимальной стоимости.

Алгоритм 7.Поиск потока минимальной стоимости.

Шаг 1. Задать нулевой поток в графе G =(V, E), то есть для всех дуг (x, y)Î E положить f (x, y)=0. Для всех вершин x Î V положить p (x)=0.

Шаг 2. Сформировать множество I, включив в него дуги (x, y), для которых p (y)- p (x)= a (x, y) и f (x, y)< c (x, y). Сформировать множество R, включив в него дуги (x, y), для которых p (y)- p (x)= a (x, y) и f (x, y)>0. Дуги, не вошедшие ни в множество I, ни в множество R, включить в множество N.

Шаг 3. Выполнить шаги 2, 3 и 4 алгоритма 5.

Шаг 4. Если увеличивающая цепь найдена, то увеличить поток вдоль найденной цепи (см. разд.7.2). В противном случае увеличить на единицу числа p (x) для всех неокрашенных (шаг 3 алгоритма 5) вершин x.

Шаг 5. Если из вершины s в вершину t передано v единиц потока или поток достиг своего максимального значения v ¢< v, то перейти к шагу 6. В противном случае перейти к шагу 2.

Шаг 6. Если из вершины s в вершину t передано v единиц потока, то поток минимальной стоимости найден. Если поток из вершины s в вершину t достиг своего максимального значения v ¢< v, то из вершины s в вершину t не может быть передано заданное число единиц потока.

Рассмотрим работу алгоритма поиска потока минимальной стоимости для графа, изображенного на рис.7.4.

Если из вершины s в вершину t требуется переслать v £2 единиц потока, то работа алгоритма завершается за три итерации, представленные в табл.7.1. После третьей итерации вершина t оказалась окрашенной. Две единицы потока из s в t посылаются по цепи (s, a), (a, b), (b, t), см. рис. 7.5.

Если v >2, то работа алгоритма поиска потока минимальной стоимости завершается за шесть итераций (табл. 7.2). После шестой итерации вершина t снова оказалась окрашенной. Одна единица потока из s в t посылается по цепи (s, b), (a, b), (a, t) (см. рис. 7.6), и суммарный поток из s в t достигает своего максимального значения, равного трем.

Таблица 7.1. Этапы поиска потока минимальной стоимости из вершины s в вершину t в графе, изображенном на рис. 7.4, согласно алгоритму 7

№ итерации	p (s)	p (a)	p (b)	p (t)	Окрашенные
					Дуги	вершины
					-	s
					(s, a)	s, a
					(s, a),(a, b)	s, a, b
					(s, a),(a, b),(b, t)	s, a, b, t

Таблица 7.2. Продолжение таблицы 7.1

№ итерации	p (s)	p (a)	p (b)	p (t)	Окрашенные
					дуги	Вершины
					-	S
					(s, b),(a, b)	s, a, b
					(s, b),(a, b),(a, t)	s, a, b, t

Упражнения:

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

2. Модифицируйте алгоритм 6 для поиска максимального потока в графе с несколькими источниками и стоками.

3. При формулировке алгоритма 7 не уточнялось, как контролировать, достиг или нет поток своего максимального значения (шаг 5). Предложите, как можно осуществлять такой контроль.

4. Реализуйте алгоритмы поиска максимального потока и поиска потока минимальной стоимости. Оцените трудоемкость алгоритмов.