Page 58 - 4336

що допускає використання в якості проміжних перших m вершин,

повинна бути не більша довжини найкоротшого шляху i в j, що

допускає використання в якості проміжних перших m-1 вершин, і

не більше довжини найкоротшого шляху з i у j, що допускає

використання в якості проміжних перших m-1 вершин і

обов'язково вершини m.

Слід відзначити, що для всіх i та m повинне бути 0.
,
Тому немає необхідності в обчисленні діагональних елементів

матриць D , D ,…, D . Крім того, для всіх i=1, 2,..., N мають
місце співвідношення:

m 1 
m
d i, m  d i, m , (4.3)
m 1 
m
d m, i  d m, i . (4.4)

Дані співвідношення обумовлюються тим, що вершина m, за

відсутності контурів від'ємної довжини, не може виступати в

якості проміжної в будь-яких найкоротших шляхах, які

починаються або закінчуються у самій вершині m. Отже, при

визначенні матриці D немає необхідності в перерахунку
елементів m-го рядка та m-го стовпця матриці D . Таким

чином, у матриці D за формулою (4.2) необхідно розрахувати
лише величини (N-1)(N-2) елементів, у число яких не входять

діагональні елементи, а також елементи з m-го рядка та m-го
стовпця.

Приклад 4.4. Використовуючи алгоритм Флойда-Уоршола,

знайти у графі, зображеному на рис. 4.8, найкоротший шлях між

усіма вершинами.

58