Page 60 - 4336

1
Елементи матриці D , d i 1 , j  min  d 0 1 , i  d 0 , 1 j ;d i 0  Відповідні
, j
шляхи

d 1 1 , 3  d 0 1 , 3  6 (3, 1)

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

d 1 3 , 3  0 -

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

d 1 1 , 4  d 0 1 , 4  1 (4, 1)

d 1 2 , 4  min  d 0 1 , 4  d 0 2 , 1 ;d 0 2 , 4  min  11 ;  2 (4, 1, 2)

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

d 1 4 , 4  0 -

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

елементів матриці D є наступними:
0 1 2 1  ) 2 , 1 ( ) 3 , 1 ( ) 4 , 1 (

D 1  2 0 4 3 , D  1  ) 1 , 2 (  ) 3 , 1 , 2 ( ) 4 , 1 , 2 ( .
6 5 0 2 ) 1 , 3 ( ) 2 , 3 (  ) 4 , 3 (

1 2 3 0 ) 1 , 4 ( ) 2 , 1 , 4 ( ) 3 , 1 , 4 ( 

Крок 2. m=2.

2
Елементи матриці D , d i 2 , j  min  d 1 2 , i  d 1 , 2 j ;d 1 , j  Відповідні
i
шляхи

d 2 1 , 1  0 -

d 2 2 , 1  d 1 2 , 1  1 (1, 2)

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

60