ВУЗ:
Составители:
Рубрика:
Таблица 9.1
Приведем теперь без дальнейших пояснений табличную форму
алгоритма Форда-Фалкерсона отыскания максимального потока.
Шаг 1. Пометить каждую строку i, для которой разность
r(s, i) – x(s, i) больше 0 меткой (s
+
, Е
i
), где Е
i
= r(s, i) – x(s, i). Если ни
одной такой метки приписать нельзя, данный поток – максимальный.
Конец.
Шаг 2. Пометить каждый непомеченный столбец j, содержащий
допустимую клетку в помеченной строке i, такую, что r(i, j) – x(i, j) больше
0 меткой (s
+
, Е
j
), где Е
j
= min(Е
i
, r(i, j) – x(i, j)). Если возможностей
несколько, выбрать любую.
Шаг 3. Пометить каждую непомеченную строку i, содержащую
допустимую клетку с ненулевым потоком в помеченном столбце j, меткой
(j
−
, Е
j
), где Е
j
= min(Е
j
, x(i, j)). Если возможностей несколько, выбрать
любую.
Шаг 4. Повторять шаги 2 и 3 до тех пор, пока или
а) не будет помечен столбец j с разностью r(j, t) – x(j, t) > 0 или
б) новых пометок приписать нельзя и для всех помеченных
столбцов r(j, t) = x(j, t). В случае
а) перейти к шагу 5, в случае б) – к
шагу 6.
Шаг 5. Найдена увеличивающая цепь от s в t. Восстановить эту цепь,
ориентируясь по меткам строк и столбцов. Увеличить потоки на всех
прямых дугах этой цепи и уменьшить потоки на всех обратных дугах этой
цепи на величину Е
т
= min(Е
j
, r(j, t) – x(j, t)). Стереть все пометки и
возвратиться к шагу 1.
Шаг 6. Данный поток максимален. Помеченные строки и столбцы
соответствуют вершинам множества R минимального разреза.
j
i
1 3
2
2 6
6
3 6
4
1 5
3
3
2
1
1
2 5
5
3
2
4
3
3 2
2
1
1
1
1
4 2
2
3
2
2
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
