Page 38 - 4387
P. 38
По закінченню даної процедури величина елемента
,
матриці визначає довжину найкоротшого шляху, що веде з
вершини i у вершину j.
= 0.
Слід відзначити, що для всіх i та m повинне бути
,
Тому немає необхідності в обчисленні діагональних елементів
матриць , ,…, . Крім того, для всіх i=1, 2,..., N мають
2
1
місце співвідношення:
m 1−
m
d i, m = d i, m , (5.2)
m
m 1 −
d m, i = d m, i . (5.3)
Приклад 5.1. Використовуючи алгоритм Флойда-Уоршола,
знайти у графі, зображеному на рис. 5.1, найкоротші шляхи між
усіма вершинами.
Рисунок 5.1.
Розв'язок.
Крок 1. Матриця є наступною:
0
0 1 2 1
D 0 = 2 0 7 ∞ .
6 5 0 2
1 ∞ 4 0
Крок 2. m=1.
37
