Нахождение потока заданной мощности минимальной стоимости. Алгоритм Басокера-Гоуэна

Задана сеть каждой дуге которой поставлено в соответствие 3 числа: С(х,у) – пропускная способность дуги, f(x,y) - , d(x,y) - стоимость провода единицы потока по дуге x,y. Требуется пропустить в сети поток заданной величины V или максимальный поток минимальной стоимости.

Алгоритм Басакера-Гоуэна

Шаг 0. Решение начинаем с нулевого потока V=0.

Шаг 1. Строим граф модифицированных стоимостей G_f по следующим правилам

1.Множество вершин графа G_f совпадает с множеством вершин графа G.

2.Если в графе G 0<f(x,y)<c(x,y) , тогда в графе строится 2 дуги: прямая, с длиной равной стоимости(e(x,y)=d(x,y)); e(x,y)=-d(x,y).

3.Если в графе G f(x,y)=0, то в графе G_f строится одна дуга e(x,y)=d(x,y).

4.Если f(x,y)=c(x,y), то рисуем e(x,y)=-d(x,y).

Шаг 2. Находим в графе G_f минимальный путь из S в T. Обозначим его P*. В исходном графе G определяем путь P, соответствующий Р*. На прямых дугах пути Р вычисляем €₁=c(x,y)-f(x,y), €₂=f(x,y), min €_1. На прямых дугах +€, на обратных -.

Шаг 3. Получаем V=V*. Если в V = заданному потоку, то алгоритм свою работу заканчивает. В графе G построим поток мощности V min стоимости.

Замечание: Если задача на нахождение максимального потока мин стоимости, то алгоритм свою работу заканчивает когда в графе G_f нет ниодного пути Р* из S в T.

Пример: построить поток V=3

t

b

S

a

4,0\5 2,0\1

3,0\1

2,0\1 3,0\6

P: s-b-a-t

S

b

t

a

P*: s-b-a-t

5 6

1

1 1

€₁=(2,3,2)=2

€=min(€_1, €_2,V)=> €=2

V*=V*₊€=2

b

a

t

S

5

-1

1 -1

-1 6

P*:s->a->b->t

P:s->a<-b->t

€₁=(4,3)=3

€₂=2

€=(3,2,1)=1