Поиск максимального потока. 4 страница

Таблица 4.1a. Заполнение левого столбца и верхней строки

№

∞

−4

∞

−4

∞

∞

∞

∞

∞

∞

∞

∞

−5

∞

∞

∞

∞

∞

Следующей операцией является заполнение левых клеток каждой из 25 ячеек. Правило заполнения достаточно простое. В ячейку с индексом (i, j) вставляется сумма чисел из i-ой клетки левого столбца и левой половины j-ой клетки верхней строки. Операция соответствует пункту 1.1 общего шага АФУ. Заметим, что для любого x (в том числе x = ∞) x + ∞ = ∞ + x = ∞. Результаты данной операции представлены в следующей таблице 4.1b.

Таблица 4.1b. Заполнение сумм

№

∞

−4

∞

∞

−4

−4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

−5

∞

−2

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

Следующая операция – изменение (в некоторых случаях) записей в средних и правых клетках всех ячеек. Правило также очень простое:

1. Если число в левой клетке меньше числа в средней клетке, то

1.1. Число из левой клетке записывается в среднюю клетку.

1.2. В правую клетку записывается номер из правой клетки верхней строки, находя-щейся в одном столбце с рассматриваемой ячейкой.

2. В противном случае ничего не делается.

В качестве примера рассмотрим ячейку (4,2) в которой число в левой клетке (5) меньше числа в средней клетке (∞). Тогда число 5 надо записать в среднюю клетку вместо ∞, а в правую клетку надо записать номер 1. Легко понять, что описанная операция (выделение минимумов и копи-рование значений) в точности представляет собой операции пунктов 1.2 и 2 общего шага АФУ. Результаты её выполнения записаны в таблице 4.1c. Заметим, что числа в средних клетках ячейки (i, j) – это длины построенных на рассматриваемой итерации и ранее путей из вершины i в вершину j, а номера в правых клетках – это предпоследние вершины на этих путях.

Таблица 4.1c. Заполнение минимумов и предпоследних вершин

№

∞

−4

∞

∞

−4

−4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

−5

∞

−2

−2

∞

∞

∞

∞

∞

∞

∞

∞

∞

Для завершения итерации 1 осталось сделать следующее. Числа из левых клеток всех яче-ек удаляются. Удаляются также все данные из левого столбца и верхней строки. В результате получаем таблицу 4.1d, которая по форме совпадает с таблицей 4, полученной в результате инициализации.

Таблица 4.1d. Результат итерации 1

№

∞

−4

∞

∞

∞

∞

∞

−5

−2

∞

∞

∞

Итерация 2.k = 2. На итерации 2 происходит последовательное преобразование данных, полученных на итерации 1 и представленных в таблице 4.1d. Естественно, что алгоритм не ме-няется, поэтому подробных объяснений к каждой таблице, как на итерации 1, не даётся. Выпол-нение итерации 2 демонстрируется в таблицах 4.2a – 4.2d, аналогичных таблицам 4.1a – 4.1d. Заметим, что в левый столбец копируются данные из 2-го столбца, а в верхнюю строку – из 2-ой строки таблицы 4.2а, так как k = 2.

Таблица 4.2а. Заполнение левого столбца и верхней строки

№

∞

∞

∞

−4

∞

∞

∞

∞

∞

−5

−2

∞

∞

∞

∞

Таблица 4.2b. Заполнение сумм

№

∞

∞

∞

∞

∞

−4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

−5

−2

∞

∞

∞

∞

∞

∞

∞

∞

∞

Таблица 4.2c. Заполнение минимумов и предпоследних вершин

№

∞

∞

∞

∞

−4

∞

∞

∞

∞

∞

∞

∞

∞

∞

−5

−2

∞

∞

∞

∞

∞

∞

∞

∞

∞

Таблица 4.2d. Результат итерации 2

№

−4

∞

∞

∞

−5

−2

∞

∞

∞

Итерация 3.k = 3. На итерации 3 происходит последовательное преобразование данных, полученных на итерации 2 и представленных в таблице 4.2d. Выполнение итерации 3 демонст-рируется в таблицах 4.3a – 4.3d.

Таблица 4.3а. Заполнение левого столбца и верхней строки

№

∞

−4

∞

∞

∞

∞

−5

−5

−2

∞

∞

∞

∞

Таблица 4.3b. Заполнение сумм

№

∞

∞

−4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

−5

∞

−1

−5

−5

−2

∞

∞

∞

∞

∞

∞

∞

∞

∞

Таблица 4.3c. Заполнение минимумов и предпоследних вершин

№

∞

∞

−4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

−5

∞

−1

−1

−5

−5

−2

∞

∞

∞

∞

∞

∞

∞

∞

∞

Таблица 4.3d. Результат итерации 3

№

−4

∞

∞

∞

−1

−5

−2

∞

∞

∞

Итерация 4.k = 4. На итерации 4 преобразование данных показано с мéньшей детализаци-ей. Требуемые операции выполняются так же, как и ранее, но промежуточные результаты не за-писываются в новые таблицы, а последовательно записываются в одни и те же ячейки и клетки. Результаты приводятся в таблице 4.4.

Таблица 4.4. Результат итерации 4

№

−1

−4

−4

−1

−1

−5

−2

Итерация 5.k = 5. Эта итерация является последней перед финальным шагом F. В таблице 4.5 содержатся кратчайшие расстояния для всех пар вершин и вершины, предпоследние на каж-дом таком пути.