Page 25 - 4861

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