Page 66 - 4336

Крок 2. m=1. Очевидно, що матриця D буде наступною:

D 1  d 1 1 , 1  0.

Крок 2. m=2.
2
Елементи матриці D Відповідні шляхи

d 2  0 -
1 , 1

d 2  min  d 1  d 0  min  0 1  1 (1, 2)
2 , 1 1 , 1 2 , 1

d 2  min  d 0 d 1  min  2 0  2 (2, 1)
1 , 2 1 , 2 1 , 1

d 2  0 -
2 , 2

Матриця D та матриця найкоротших шляхів D для

елементів матриці D є наступними:

D 2  0 1 , D  2   , 1 ( ) 2 .
2 0 ) 1 , 2 ( 

Слід відзначити, що наведені результати ідентичні даним,

розташованим у лівій верхній підматриці розмірністю 2×2

матриці D , що одержана в прикладі 4.4 за допомогою алгоритму

Флойда-Уоршола.
Крок 2. m=3.

Відповідні
3
Елементи матриці D
шляхи

d 3 1 , 1  d 3 2 , 2  d 3 3 , 3  0 -

d 3  min  d 2  d 0 ;d 2  d 0  min  0 1 ; 2  7  2 (1, 3)
3 , 1 1 , 1 3 , 1 2 , 1 3 , 2

d 3  min  d 2  d 0 ;d 2  d 0  min  2 0 ; 2  7  4 (2, 1), (1, 3)
3 , 2 1 , 2 3 , 1 2 , 2 3 , 2

d 3 1 , 3  min  d 0 1 , 3  d 2 1 , 1 ;d 0 2 , 3 d 2 1 , 2  min  6 5 ; 0  2  6 (3, 1)

66