Поиск максимального потока. 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 содержатся кратчайшие расстояния для всех пар вершин и вершины, предпоследние на каж-дом таком пути.

Наши рекомендации