Page 47 - 4387

Крок 2. m=2.

2
Елементи матриці D Відповідні шляхи

d 2 1 , 1 = 0 -

d 2 2 , 1 = min { d 1 1 , 1 + d 0 2 , 1 } min += {0 1 = (1, 2)
} 1

d 2 1 , 2 = min { d 0 1 , 2 + d 1 1 , 1 } min += {2 0 = (2, 1)
} 2

d 2 2 , 2 = 0 -

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

Слід відзначити, що наведені результати ідентичні даним,

розташованим у лівій верхній підматриці розмірністю 2×2

матриці , що одержана в прикладі 5.1 за допомогою алгоритму
2
Флойда-Уоршола.

Крок 2. m=3.

Відповідні
3
Елементи матриці D
шляхи

d 3 1 , 1 = d 3 2 , 2 = d 3 3 , 3 = 0 -

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

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

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

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

46