7.2 Багатополюсні найкоротші ланцюги
Тепер будемо шукати найкоротші ланцюги між всіма парами вузлів мережі. Будемо допускати, що довжини дуг можуть бути і від’ємними. При цьому як і раніше у силі залишається вимога: сума дуг по будь-якому направленому циклу повинна бути невід’ємною.
У довільній мережі лише деякі дуги будуть найкоротшими ланцюгами із в , такі дуги будемо називати базисними. Відмітимо, у 7.1 всі дуги були базисними.
Допустимо, що
відомий найкоротший ланцюг, наприклад,
із
в
.
Тоді цей ланцюг повинен складатись
тільки із базисних дуг у противному
разі він не буде найкоротшим. Якщо тепер
ввести дугу
з довжиною, яка дорівнює довжині ланцюга,
що розглядається із
в
,
то ця дуга буде базисною.
Задачу знаходження найкоротших ланцюгів між всіма парами вузлів можна розв’язати, добавивши базисні дуги (якщо таких дуг у мережі не було) між всіма парами вузлів. При добавленні базисної дуги її ставиться у відповідність дуга, яка дорівнює довжині найкоротшого ланцюга, що складається із базисних дуг вихідної мережі.
Розглянемо наступну операцію, що визначена для фіксованого вузла :
.
(7.2)
Цю операцію будемо називати тернарною.
При
здійсненні операції (7.2) порівнюється
довжина
дуги
і довжина ланцюга
,
а потім довжині дуги присвоюється
значення
,
якщо
.
Виявляється, якщо
виконувати операцію (7.2) послідовно для
кожного вузла
,
то отримані в результаті значення
будуть довжинами найкоротших ланцюгів
між всіма парами вузлів. При цьому обсяг
обчислень не перевершує
операцій додавання і порівняння.
Ідея доказу цього факту полягає у наступному. Нехай - проміжний вузол в найкоротшому ланцюгу із в , що має найменший індекс, а і два вузла, які є сусідніми з в цьому ланцюгові. При обчисленні за формулою (7.2) виходить, що , і ми вводимо нову дугу довжини . Таким чином, для дуги твердження доказано. Тепер замінено найкоротший ланцюг із в другою, що вміщує нову дугу ; цей ланцюг має ту же довжину, але менше число вузлів. Дальше продовжуємо міркування за індукцією.
Щоб прослідкувати,
які дуги початкової мережі входять до
найкоротшого ланцюга, побудуємо довідкову
таблицю, яка заповнюється у
міру виконання операції (7.2). З початку
елемент
таблиці, який знаходиться на перетині
-ого
рядка і
-ого
стовпця, вважаємо рівним
.
Після виконання операції (7.2) нехай
елемент
вказує на перший проміжний вузол у
найкоротшому ланцюгу між
і
,
якщо такий вузол існує. Якщо такого
проміжного вузла не існує, то вважаємо
елемент
рівним
.
Таким чином,
(7.3)
В усіх обчисленнях
ми до цих пір допускали, що
.
Якщо допустити, що
,
а в операції (7.2) дозволити, щоб
,
то послідовне виконання операції (7.2),
дає можливість знайти найкоротші цикли,
що вміщують вузол
.
Якщо при таких обчисленнях величина
набуває від’ємного значення, то це
означає, що у мережі існує від’ємний
цикл, тобто
такий, в якого сума довжин складових
дуг від’ємна.
Приклад 7.2. Для мережі, яка показана на рис. 7.2 знайти найкоротші ланцюги між всіма парами вузлів. Довжини дуг вказані у табл. 7.1.
Рисунок 7.2 – Мережа разом з довжинами дуг
Виконання операції
(7.2) при
,
полягає у тому, що перераховуються всі
елементи табл. 7.1, що не належать першому
рядку або першому стовпцю.
Таблиця 7.1 – Довжини дуг між вузлами мережі (початкові)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
|
|
|
|
2 |
11 |
0 |
|
12 |
2 |
|
|
|
3 |
30 |
|
0 |
19 |
|
4 |
|
|
4 |
|
12 |
19 |
0 |
11 |
9 |
|
|
5 |
|
2 |
|
11 |
0 |
|
|
|
6 |
|
|
4 |
9 |
|
0 |
|
|
7 |
|
|
|
20 |
1 |
1 |
0 |
|
Маємо:
для другого рядка
-
,
,
,
тобто
;
:
,
:
,
:
,
:
,
:
;
для третього
рядка -
,
,
,
,
тобто
;
:
,
:
,
:
,
:
,
:
;
для четвертого
рядка -
,
,
,
,
тобто
;
:
,
:
,
:
,
:
,
:
;
для п’ятого
рядка -
,
,
,
,
тобто
;
:
,
:
,
:
,
:
,
:
;
для шостого рядка
-
,
,
,
,
тобто
;
:
,
:
,
:
,
:
,
:
;
для сьомого рядка
-
,
,
,
тобто
;
:
,
:
,
:
,
:
,
:
,
Результати першого
етапу обчислень заносимо у табл. 7.2,
аналіз якої показує, що змінились тільки
величини
і
.
Таблиця 7.2 – Довжини дуг між вузлами мережі (після першого етапу)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
|
|
|
|
2 |
11 |
0 |
41 |
12 |
2 |
|
|
|
3 |
30 |
41 |
0 |
19 |
|
4 |
|
|
4 |
|
12 |
19 |
0 |
11 |
9 |
|
|
5 |
|
2 |
|
11 |
0 |
|
|
|
6 |
|
|
4 |
9 |
|
0 |
|
|
7 |
|
|
|
20 |
1 |
1 |
0 |
|
Виконання операції
(7.2) при
полягає у тому, що перераховуються всі
елементи табл. 7.2, крім елементів, які
знаходяться у другому рядку і у другому
стовпці. Обчислення проводимо аналогічно
першому етапу. Будемо обчислювати
довжини лише тих дух, значення яких
змінюється на другому етапі обчислень.
Маємо
,
:
,
,
:
,
:
,
,
:
,
,
,
,
;
інші елементи табл. 7.2 залишаються незмінними. Результати обчислень другого етапу заносимо у табл. 7.3.
Таблиця 7.3 – Довжини дуг між вузлами мережі (після другого етапу)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
23 |
13 |
|
|
2 |
11 |
0 |
41 |
12 |
2 |
|
|
|
3 |
30 |
41 |
0 |
19 |
43 |
4 |
|
|
4 |
23 |
12 |
19 |
0 |
11 |
9 |
|
|
5 |
13 |
2 |
43 |
11 |
0 |
|
|
|
6 |
|
|
4 |
9 |
|
0 |
|
|
7 |
|
|
|
20 |
1 |
1 |
0 |
|
Переходимо тепер
до третього етапу обчислень, де
.
Із процесу обчислень виключаємо третій
рядок і третій стовпець (табл. 7.3). Наведемо
обчислення за формулою (7.2) для тих довжин
дуг, значення яких змінилось на третьому
етапі обчислень. Маємо
,
:
,
,
:
,
,
:
,
,
,
;
інші елементи табл. 7.3 залишаються без зміни. У табл. 7.4 заносимо результати обчислень третього етапу.
Таблиця 7.4 – Довжини дуг між вузлами мережі (після третього етапу)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
23 |
13 |
34 |
|
2 |
11 |
0 |
41 |
12 |
2 |
45 |
|
|
3 |
30 |
41 |
0 |
19 |
43 |
4 |
|
|
4 |
23 |
12 |
19 |
0 |
11 |
9 |
|
|
5 |
13 |
2 |
43 |
11 |
0 |
47 |
|
|
6 |
34 |
45 |
4 |
9 |
47 |
0 |
|
|
7 |
|
|
|
20 |
1 |
1 |
0 |
|
Тепер візьмемо
.
Це означає, що ми переходимо до четвертого
етапу обчислень, у якому не беруть участі
четверта лінійка і четвертий стовпець.
На цьому етапі обчислень використовуємо
табл. 7.4. У наступну табл. 7.5 заносимо
тільки ті значення довжин дуг, які
змінилися у процесі реалізації четвертого
етапу. Отже,
,
:
,
,
:
,
:
,
,
:
,
,
:
,
,
:
,
:
,
,
,
,
,
;
інші елементи табл. 7.4 залишаються без зміни. Занесемо у табл. 7.5 результати обчислень четвертого етапу.
Таблиця 7.5 – Довжини дуг між вузлами мережі (після четвертого етапу)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
23 |
13 |
32 |
|
2 |
11 |
0 |
31 |
12 |
2 |
21 |
|
|
3 |
30 |
31 |
0 |
19 |
30 |
4 |
|
|
4 |
23 |
12 |
19 |
0 |
11 |
9 |
|
|
5 |
13 |
2 |
30 |
11 |
0 |
20 |
|
|
6 |
32 |
21 |
4 |
9 |
20 |
0 |
|
|
7 |
43 |
32 |
39 |
20 |
1 |
1 |
0 |
|
Реалізацію п’ятого
етапу (
)
здійснюємо на основі табл. 7.5. На цьому
етапі не приймають участь в обчисленнях
п’ятий рядок і п’ятий стовпець (табл.
7.5). На цьому етапі здійснюємо обчислення
лише для тих довжин дуг, значення яких
змінюється у процесі таких обчислень.
,
:
,
:
,
:
,
:
;
інші елементи таблиці залишаються незмінними. У табл. 7.6 заносимо результати обчислень п’ятого етапу.
Таблиця 7.6 – Довжини дуг між вузлами мережі (після п’ятого етапу)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
23 |
13 |
32 |
|
2 |
11 |
0 |
31 |
12 |
2 |
21 |
|
|
3 |
30 |
31 |
0 |
19 |
30 |
4 |
|
|
4 |
23 |
12 |
19 |
0 |
11 |
9 |
|
|
5 |
13 |
2 |
30 |
11 |
0 |
20 |
|
|
6 |
32 |
21 |
4 |
9 |
20 |
0 |
|
|
7 |
43 |
32 |
39 |
20 |
1 |
1 |
0 |
|
Переходимо тепер
до шостого етапу обчислень коли,
.
У відповідності з формулою (7.2)
,
тобто із процесу обчислень виключаємо
шостий рядок і шостий стовпець табл.
7.6. Як і раніше обчислення проводимо
лише для тих довжин дуг, значення яких
змінюється при переході до шостого
етапу обчислень. Маємо
,
:
,
,
:
,
:
,
,
:
,
:
.
, , ;
інші елементи
табл. 7.6 залишаються без змін. Результати
обчислень шостого етапу заносимо у
табл. 7.7. Ця таблиця буде остаточною,
оскільки довжини дуг сьомого стовпця
при
дорівнюють нескінченності, то при
реалізації сьомого етапу обчислень
елементи табл. 7.7 не змінять своє значення.
На основі табл.
7.7 складемо довідкову таблицю 7.8. На
початку елемент
таблиці, який знаходиться на перетині
го
рядка і
- го стовпця, кладемо рівним
.
У табл. 7.7 елемент
вказує на найкоротший ланцюг між вузлами
і
.
Якщо у вибраному найкоротшому ланцюгу
-
найближчим
до вузла
є вузол
,
тоді у табл. 7.8 на пересіченні
-го
рядка і
-го
стовпця вписуємо значення
.
Якщо такого найближчого вузла не існує
то значення відповідного елемента
таблиці не змінюється. Нехай
Таблиця 7.7 – Довжини дуг між вузлами мережі (після шостого та сьомого етапів)
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
0 |
11 |
30 |
23 |
13 |
32 |
|
2 |
11 |
0 |
25 |
12 |
2 |
21 |
|
|
3 |
30 |
25 |
0 |
13 |
24 |
4 |
|
|
4 |
23 |
12 |
13 |
0 |
11 |
9 |
|
|
5 |
13 |
2 |
30 |
11 |
0 |
20 |
|
|
6 |
32 |
21 |
4 |
9 |
20 |
0 |
|
|
7 |
14 |
3 |
5 |
10 |
1 |
1 |
0 |
|
,
а
=6.
Із табл. 7.8 знаходимо, що
.
Знаходимо ланцюг довжини 32 (рис. 7.2).
таким ланцюгом буде 1 – 2 – 4 – 6. Найближчим
вузлом до вузла 1 буде вузол 2. Тому в
клітинку (1, 6) табл. 7.8 цифру 6 замінюємо
на цифру 2. Тепер, нехай
=5.
Із табл. 7.7 знаходимо, що
.
Цьому значенню відповідає ланцюг 1 – 2
– 5. Отже, найближчим до вузла 1 є вузол
2. Це значення заносимо до клітинки (1,
5) табл. 7.8. Аналогічно заповнюємо і інші
клітинки табл. 7.8.
Якщо потрібно
знайти найкоротший ланцюг із
в
,
то за довідковою таблицею спочатку
знаходимо елемент
,
який означає, що вузол
є найближчим до вузла
.
Потім знаходимо елемент
,
який вказує на перший проміжний елемент
у найкоротшому ланцюгу із
в
.
Цей процес продовжується до знаходження
елементу
,
який означає, що знайдені всі вузли, що
входять у найкоротший ланцюг
-
,
а саме
,
,
…,
,
.
|
В у з л и |
|||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||
В у з л и |
1 |
1 |
2 |
3 |
2 |
2 |
2 |
7 |
2 |
1 |
2 |
4 |
4 |
5 |
4 |
7 |
|
3 |
1 |
6 |
3 |
6 |
6 |
6 |
7 |
|
4 |
2 |
2 |
6 |
4 |
5 |
6 |
7 |
|
5 |
2 |
2 |
4 |
4 |
5 |
4 |
7 |
|
6 |
4 |
4 |
3 |
4 |
4 |
6 |
7 |
|
7 |
5 |
5 |
6 |
6 |
5 |
6 |
7 |
|
Нехай, наприклад, потрібно знайти найкоротший ланцюг із до . Тоді із табл. 7.8 спочатку знаходимо елемент (1, 6) = 2. Потім знаходимо (2, 6) = 4 і (4, 6) = 6. Отже, найкоротший ланцюг і до проходить через вузли і .