Page 25 - 4861
P. 25

9 БАГАТОПОЛЮСНІ НАЙКОРОТШІ ЛАНЦЮГИ

                 Припустимо, що є мережа, у якій кожній дузі  A  поставлена у відповідність довжина, або
                                                                     ij
             віддаль d .  Довжиною  ланцюга  називається  сума  довжин    d ,  яка  взята за  всіма  дугами  цього
                       ij                                                     ij
             ланцюга. Необхідно знайти ланцюг мінімальної довжини із заданого вузла  N  у заданий вузол
                                                                                                s
              N .  Будемо  вважати,  що  d  .  Якщо  деяка  пара  вузлів  N   і  N   не  зв’язана  безпосередньо
                                               0
                f                          ij                                  i     j
                                                               0
             дугою,  то  вважаємо  d   .  Крім  того  d  .  Відмітимо,  що  величини  d   не  обов’язково
                                      ij                   ii                                   ij
             повинні задовольняти умові симетричності  d       d .
                                                            ij   ji
                 Будемо шукати найкоротші ланцюги між всіма парами вузлів мережі. Будемо допускати, що
             довжини дуг  d  можуть бути і від’ємними. При цьому як і раніше у силі залишається вимога:
                             ij
             сума дуг по будь-якому направленому циклу повинна бути невід’ємною.
                 У довільній мережі лише деякі дуги  A  будуть найкоротшими ланцюгами із  N  в  N , такі
                                                          ij                                          i     j
             дуги будемо називати базисними.
                 Припустимо,  що  відомий  найкоротший  ланцюг,  наприклад,  із  N   в  N .  Тоді  цей  ланцюг
                                                                                       p      q
             повинен складатись тільки  із базисних дуг  у  противному разі він не буде найкоротшим. Якщо
             тепер ввести дугу  A  з довжиною, яка дорівнює довжині ланцюга, що розглядається із  N  в  N ,
                                  pq                                                                       p     q
             то ця дуга буде базисною.
                     Задачу  знаходження  найкоротших  ланцюгів  між  всіма  парами  вузлів  можна  розв’язати,
             добавивши  базисні  дуги  (якщо  таких  дуг  у  мережі  не  було)  між  всіма  парами  вузлів.  При
             добавленні базисної дуги її ставиться у відповідність дуга, яка дорівнює довжині найкоротшого
             ланцюга, що складається із базисних дуг вихідної мережі.
                     Розглянемо наступну операцію, яка визначена для фіксованого вузла  N :
                                                                                              j

                                                                           i
                                                           ,
                                               d   min d d    d            j .                      (9.1)
                                                                              k
                                                ik        ik  ij  jk
                     Цю операцію будемо називати тернарною.
                     При  здійсненні  операції  (9.2)  порівнюється  довжина  d   дуги  A   і  довжина  ланцюга
                                                                                ik         ik
              N   N   N , а потім довжині дуги присвоюється значення d      d , якщо d     d   d .
                i    j   k                                                  ij   jk        ik   ij   jk
                                                                                                       j 
                     Виявляється, якщо виконувати операцію (9.1) послідовно для кожного вузла  N   j        1,   n ,
             то  отримані  в  результаті  значення  d   будуть  довжинами  найкоротших  ланцюгів  між  всіма
                                                      ik
             парами вузлів. При цьому обсяг обчислень не перевершує   n n       1 n    2  операцій додавання  і

             порівняння.
                 Щоб  прослідкувати,  які  дуги  початкової  мережі  входять  до  найкоротшого  ланцюга,
             побудуємо  довідкову  таблицю,  яка  заповнюється  у  міру  виконання  операції  (9.2).  З  початку
                           
             елемент   ,i k   таблиці,  який  знаходиться  на  перетині  i -ого  рядка  і  k -ого  стовпця,  вважаємо
                                                                            
             рівним  k . Після виконання операції (9.2) нехай елемент  ,i k  вказує на перший проміжний вузол
             у найкоротшому ланцюгу між  N  і  N , якщо такий вузол існує. Якщо такого проміжного вузла
                                                i    k
                                                 
             не існує, то вважаємо елемент  ,i k  рівним  k .
                 Таким чином,
                                                          , якщоi j  d   d   d  jk  ,
                                                          ,
                                                        
                                                                           ij
                                                                      ik
                                                  , i
                                                   k                                                              (9.2)
                                                           ,
                                                           , якщоi k  d   d   d  jk .
                                                                      ik
                                                                           ij
                 У всіх обчисленнях ми до цих пір допускали, що  d      0, i . Якщо допустити, що d     , i , а
                                                                      ii                               ii
                                                               24
   20   21   22   23   24   25   26   27   28   29   30