Page 60 - 4336
P. 60
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