Page 40 - 4387

Матриця та матриця найкоротших шляхів для
′
1
1
елементів матриці є наступними:
1
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 = min { d 1 2 , i + d 1 , 2 j ;d i 1 , j } Відповідні
, j
шляхи

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)
=
=
d 2 4 , 1 = min { d 1 2 , 1 + d 1 4 , 2 ;d 1 4 , 1 } min { 1+ 1 ; 3 } 1 (1, 4)

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

d 2 2 , 2 = 0 -

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

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

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

d 2 2 , 3 = d 1 2 , 3 = 5 (3, 2)

d 2 3 , 3 = 0 -

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

39