Page 26 - 4861

в операції (9.1) дозволити, щоб i  , то послідовне виконання операції (9.1), дає можливість
k
знайти найкоротші цикли, що вміщують вузол N . Якщо при таких обчисленнях величина d
i ii
набуває від’ємного значення, то це означає, що у мережі існує від’ємний цикл, тобто такий, в
якого сума довжин складових дуг від’ємна.

10 ПРИКЛАД ЗНАХОДЖЕННЯ БАГАТОПОЛЮСНИХ НАЙКОРОТШИХ ШЛЯХІВ

Для мережі, яка показана на рис. 10.1 знайти найкоротші ланцюги між всіма парами вузлів
шляхом побудови довідкової таблиці.

Рисунок 10.1 – Мережа разом з довжинами дуг

На основі рис. 10.1 складаємо таблицю, у яку заносимо довжини неорієнтованих дуг.

Таблиця 10.1 – Довжини дуг між вузлами мережі (початкова)

1 2 3 4 5 6 7 8 9 10
1 0 5  7   14   
2 5 0 9 2      
3  9 0  1 8    
4 7 2  0 10  25 21  
5   1 10 0    13 
6   8   0   4 3
7 14   25   0 19  
8    21   19 0 9 6
9     13 4  9 0 
10      3  6  0

У середовищі MatLab складаємо програму розрахунку найкоротших шляхів між всіма порами
вузлів мережі.
Лістинг 10.1 – Файл – програма обчислення найкоротших шляхів між всіма парами вузлів
мережі
%======================================
%Багатополюсні найкоротші ланцюги
%======================================
%Довжини дуг між вузлами мережі
d=[0 5 Inf 7 Inf Inf 14 Inf Inf Inf;...
5 0 9 2 Inf Inf Inf Inf Inf Inf;...
Inf 9 0 Inf 1 8 Inf Inf Inf Inf;...
7 2 Inf 0 10 Inf 25 21 Inf Inf;...
Inf Inf 1 10 0 Inf Inf Inf 13 Inf;...

25