Page 27 - 4861

Inf Inf 8 Inf Inf 0 Inf Inf 4 3;...
14 Inf Inf 25 Inf Inf 0 19 Inf Inf;...
Inf Inf Inf 21 Inf Inf 19 0 9 6;...
Inf Inf Inf Inf 13 4 Inf 9 0 Inf;...
Inf Inf Inf Inf Inf 3 Inf 6 Inf 0];
%--------------------------------------
%Тернарна операція
N=size(d);
for j=1:N
for i=1:N
for k=1:N
if and(k~=j,i~=j)
d(i,k)=min(d(i,k),d(i,j)+d(j,k));
end
end
end
end

Результат розрахунку за складеною програмою заносимо у табл. 10.2.

Таблиця 10.2 – Довжини дуг між вузлами мережі

1 2 3 4 5 6 7 8 9 10
1 0 5 14 7 15 22 14 28 26 25
2 5 0 9 2 10 17 19 23 21 20
3 14 9 0 11 1 8 28 17 12 11
4 7 2 11 0 10 19 21 21 23 22
5 15 10 1 10 0 9 29 18 13 12
6 22 17 8 19 9 0 28 9 4 3
7 14 19 28 21 29 28 0 19 28 25
8 28 23 17 21 18 9 19 0 9 6
9 26 21 12 23 13 4 28 9 0 7
10 25 20 11 22 12 3 25 6 7 0


На основі таблиці 10.2 складемо довідкову таблицю 10.3. На початку елемент  ,i k таблиці,
який знаходиться на перетині i  го рядка і k - го стовпця, кладемо рівним k . У табл. 10.2

елемент  ,p q вказує на найкоротший ланцюг між вузлами N і N . Якщо у вибраному
q
p
найкоротшому ланцюгу N - N найближчим до вузла N є вузол N , тоді у табл. 10.3 на
p q p j
пересіченні p -го рядка і q -го стовпця вписуємо значення j . Якщо такого найближчого вузла не
існує то значення відповідного елемента таблиці не змінюється. Нехай p  1, а q =6. Із табл. 10.2
знаходимо, що d  22 . Знаходимо ланцюг довжини 22 (рис. 10.1). таким ланцюгом буде 1 – 2 –
16
3 – 6. Найближчим вузлом до вузла 1 буде вузол 2. Тому в клітинку (1, 6) табл. 10.3 цифру 6
замінюємо на цифру 2. Тепер, нехай q =5. Із табл. 10.7 знаходимо, що d  15. Цьому значенню
15
відповідає ланцюг 1 – 2 – 3 - 5. Отже, найближчим до вузла 1 є вузол 2. Це значення заносимо до
клітинки (1, 5) табл. 10.3. Аналогічно заповнюємо і інші клітинки табл. 10.3.
Якщо потрібно знайти найкоротший ланцюг із N в N , то за довідковою таблицею
p q
спочатку знаходимо елемент  ,p q  k , який означає, що вузол N є найближчим до вузла p .
k

Потім знаходимо елемент  ,k q , який вказує на перший проміжний елемент у найкоротшому

ланцюгу із N в N . Цей процес продовжується до знаходження елементу  ,i q  , який
q
k q

26