Page 41 - 4387

2
Елементи матриці D , d i 2 = min { d 1 2 , i + d 1 , 2 j ;d 1 , j } Відповідні
i
, j
шляхи
d 2 1 , 4 = min { d 1 2 , 4 + d 1 1 , 2 ;d 1 1 , 4 } min += {2 1 ; 2 } 1= (4, 1)

d 2 = d 1 = 2 (4, 1, 2)
2 , 4 2 , 4

=
d 2 3 , 4 = min { d 1 2 , 4 + d 1 3 , 2 ;d 1 3 , 4 } min += {2 3 ; 4 } 3 (4, 3)

d 2 4 , 4 = 0 -

′
Матриця та матриця найкоротших шляхів для
2
2
елементів матриці є наступними:
2
0 1 2 1 − ) 2 , 1 ( ) 3 , 1 ( ) 4 , 1 (

D 2 = 2 0 4 3 , D ′ 2 = ) 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 ( −

Аналогічним чином визначаються елементи матриць та
3
і відповідні їм матриці найкоротших шляхів. Одержані
4
результати наведені нижче.

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

D 3 = 2 0 4 3 , D ′ 3 = ) 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 ( −

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

D 4 = 2 0 4 3 ,D ′ 4 = ) 1 , 2 ( − ) 3 , 1 , 2 ( ) 4 , 1 , 2 (
3 4 0 2 ) 1 , 4 , 3 ( ) 2 , 1 , 4 , 3 ( − ) 4 , 3 (

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

40