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