Page 39 - 4387

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

d 1 1 , 1 = d 0 1 , 1 = 0 -

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

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

d 1 4 , 1 = d 0 4 , 1 = 1 (1, 4)

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

d 1 2 , 2 = 0 -

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

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

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 + 5 ; 1 } 5 (3, 2)
=
{6
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 -

38