Алгоритм Форда нахождения максимального потока на сети

Исходные данные заносятся в таблицу размерности (n+1) Ч (n+1). Если дуга, то в соответствующей клетке таблицы записывается значение d_ij.

Если обратная дуга, то в соответствующей клетке записывается значение d_ji, если дуга, то в клетке (j, i) записывается Ш.

Если дуги, , то соответствующие клетки остаются пустыми. Итак, заполненными будут только клетки, симметричные относительно главной диагонали.

Каждый шаг алгоритма Форда состоит из трёх действий.

1. Находится путь по таблице из узлаистока Ш в узел-сток n с пропускной способностью больше 0. Для этого столбец, соответствующий узлу-истоку, отмечается знаком *. Далее отыскиваются в строке с номером 0 элементы dij > 0 и столбцы, в которых они находятся, отмечаются сверху номером просматриваемой строки (цифрой 0). В результате окажутся выделенными все дуги (0, j) c положительными пропускными способностями. Эти дуги могут служить первыми дугами пути из истока в сток.

Далее просматриваются те строки, номера которых совпадают с номерами отмеченных столбцов. В каждой такой строке i отыскиваются элементы d_ij > 0, находящиеся в непомеченных столбцах, и эти столбцы отмечаются номером просматриваемой строки. Таким образом, окажутся выделенными дуги, которые могут служить вторыми дугами путей из истока в сток.

Аналогичный просмотр строк продолжается до тех пор, пока: а) либо не будет помечен столбец с номером n (сток) что означает выделение пути с пропускной способностью больше нуля из истока в сток; б) либо нельзя помечать новые столбцы (в просматриваемых строках не окажется положительных элементов), при этом столбец с номером n также останется не отмеченным.

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

В случае «а» искомый путь µ из источника в сток находится используя пометки столбцов. Пусть последний столбец n помечен номером k, тогда дуга (k, n) последнее звено искомого пути. Далее просматривается столбец с номером k, пусть отметка этого столбца l. Тогда дуга (l, k) предпоследнее звено искомого пути и т. д.Этот процесс продолжается до тех пор, пока не найдётся отметка *, т. е. отметка истока Ш. Пусть эта отметка будет цифра m. Таким образом путь от истока к стоку будет состоять из дуг µ=((Ш, m),…, (l, k), (k, n)). (5).

2. Клетки, соответствующие дугам этого пути, отмечаются знаком (-), а симметричные им клетки, т. е. соответствующие обратным дугам — знаком (+). По найденному пути (5) можно пропустить максимально возможный поток, величина которого равна И =min { dij- }.Эта величина И отнимается от всех пропускных способностей клеток, отмеченных знаком (-) и прибавляется к пропускным способностям клеток, отмеченных знаком (+). В результате получается новая таблица, в которой записаны неиспользованные пропускные способности дуг после пропускания максимального потока по пути (5).

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

Это процесс продолжается до тех пор, пока не будет иметь место случай б).

3. Пусть имеется случай б), т. е. когда не существует пути из истока в сток, состоящий из дуг с неиспользованными пропускными способностями. Это означает, что найдены все возможные пути перевозки продукции и задача решена.

Для определения максимального потока на сети V^* в последней таблице выделяются отмеченные столбцы, номера которых образуют множество R^*, причём исток ^*. В результате получается минимальный разрез (R^*,^*) и по теореме ФордаФалкерсона.

Для нахождения значений потоков по дугам x_ij^*, образующих поток V^* из элементов первой таблицы вычитаются соответствующие элементы последней таблицы.

Если в клетке получается неотрицательная величина, то она оставляется; если — отрицательная, то в клетке записывается. Значения заполненных клеток будут соответствовать потокам по дугам x_ij^*. Причём.

Пример. На данной сети определить максимальный поток из узла в узел 4.

1. * 0 0 1 2.

И₁= min (19,9)=9.

2. * 0 0 1 3.

И₂= min (17,12,24)=12.

3. * 0 0 2 3.

И₃= min (10,8,12)=8.

4. * 0 0 1 2.

Пути из 0 в 4 нет! Определяются множества: R*={0,1,2}, ={3,4}.

(R^*,^*)=((1,3),(2,3),(2,4)).

d (R^*,^*)=V^*=12+8+9=29.

5. В заключительной таблице положительные элементы определяют потоки по дугам xij*.