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