Домашня робота ТА 2

D6=	0	∞	∞	∞	∞	∞	∞	28
	14	0	∞	∞	31	53	88	42
	∞	∞	0	20	∞	9	38	35
	∞	∞	∞	0	∞	∞	18	15
	∞	∞	∞	∞	0	22	57	∞
	∞	∞	∞	∞	∞	0	35	∞
	∞	∞	∞	∞	∞	∞	0	∞
	∞	∞	∞	∞	∞	∞	∞	0

На основании матрицы D⁶, вычислим последовательно все элементы матрицы D⁷. Для этого мы используем рекуррентное соотношение d_i,j⁷=min{ d_i,7⁶+ d_7,j⁶; d_i,j⁶}. d_1,1⁷=min{d_1,7⁶+d_7,1⁶d_1,1⁶}=min{∞+∞; 0}=0 d_1,2⁷=min{d_1,7⁶+d_7,2⁶d_1,2⁶}=min{∞+∞; ∞}=∞ d_1,3⁷=min{d_1,7⁶+d_7,3⁶d_1,3⁶}=min{∞+∞; ∞}=∞ d_1,4⁷=min{d_1,7⁶+d_7,4⁶d_1,4⁶}=min{∞+∞; ∞}=∞ d_1,5⁷=min{d_1,7⁶+d_7,5⁶d_1,5⁶}=min{∞+∞; ∞}=∞ d_1,6⁷=min{d_1,7⁶+d_7,6⁶d_1,6⁶}=min{∞+∞; ∞}=∞ d_1,7⁷=min{d_1,7⁶+d_7,7⁶d_1,7⁶}=min{∞+0; ∞}=∞ d_1,8⁷=min{d_1,7⁶+d_7,8⁶d_1,8⁶}=min{∞+∞; 28}=28 d_2,1⁷=min{d_2,7⁶+d_7,1⁶d_2,1⁶}=min{88+∞; 14}=14 d_2,2⁷=min{d_2,7⁶+d_7,2⁶d_2,2⁶}=min{88+∞; 0}=0 d_2,3⁷=min{d_2,7⁶+d_7,3⁶d_2,3⁶}=min{88+∞; ∞}=∞ d_2,4⁷=min{d_2,7⁶+d_7,4⁶d_2,4⁶}=min{88+∞; ∞}=∞ d_2,5⁷=min{d_2,7⁶+d_7,5⁶d_2,5⁶}=min{88+∞; 31}=31 d_2,6⁷=min{d_2,7⁶+d_7,6⁶d_2,6⁶}=min{88+∞; 53}=53 d_2,7⁷=min{d_2,7⁶+d_7,7⁶d_2,7⁶}=min{88+0; 88}=88 d_2,8⁷=min{d_2,7⁶+d_7,8⁶d_2,8⁶}=min{88+∞; 42}=42 d_3,1⁷=min{d_3,7⁶+d_7,1⁶d_3,1⁶}=min{38+∞; ∞}=∞ d_3,2⁷=min{d_3,7⁶+d_7,2⁶d_3,2⁶}=min{38+∞; ∞}=∞ d_3,3⁷=min{d_3,7⁶+d_7,3⁶d_3,3⁶}=min{38+∞; 0}=0 d_3,4⁷=min{d_3,7⁶+d_7,4⁶d_3,4⁶}=min{38+∞; 20}=20 d_3,5⁷=min{d_3,7⁶+d_7,5⁶d_3,5⁶}=min{38+∞; ∞}=∞ d_3,6⁷=min{d_3,7⁶+d_7,6⁶d_3,6⁶}=min{38+∞; 9}=9 d_3,7⁷=min{d_3,7⁶+d_7,7⁶d_3,7⁶}=min{38+0; 38}=38 d_3,8⁷=min{d_3,7⁶+d_7,8⁶d_3,8⁶}=min{38+∞; 35}=35 d_4,1⁷=min{d_4,7⁶+d_7,1⁶d_4,1⁶}=min{18+∞; ∞}=∞ d_4,2⁷=min{d_4,7⁶+d_7,2⁶d_4,2⁶}=min{18+∞; ∞}=∞ d_4,3⁷=min{d_4,7⁶+d_7,3⁶d_4,3⁶}=min{18+∞; ∞}=∞ d_4,4⁷=min{d_4,7⁶+d_7,4⁶d_4,4⁶}=min{18+∞; 0}=0 d_4,5⁷=min{d_4,7⁶+d_7,5⁶d_4,5⁶}=min{18+∞; ∞}=∞ d_4,6⁷=min{d_4,7⁶+d_7,6⁶d_4,6⁶}=min{18+∞; ∞}=∞ d_4,7⁷=min{d_4,7⁶+d_7,7⁶d_4,7⁶}=min{18+0; 18}=18 d_4,8⁷=min{d_4,7⁶+d_7,8⁶d_4,8⁶}=min{18+∞; 15}=15 d_5,1⁷=min{d_5,7⁶+d_7,1⁶d_5,1⁶}=min{57+∞; ∞}=∞ d_5,2⁷=min{d_5,7⁶+d_7,2⁶d_5,2⁶}=min{57+∞; ∞}=∞ d_5,3⁷=min{d_5,7⁶+d_7,3⁶d_5,3⁶}=min{57+∞; ∞}=∞ d_5,4⁷=min{d_5,7⁶+d_7,4⁶d_5,4⁶}=min{57+∞; ∞}=∞ d_5,5⁷=min{d_5,7⁶+d_7,5⁶d_5,5⁶}=min{57+∞; 0}=0 d_5,6⁷=min{d_5,7⁶+d_7,6⁶d_5,6⁶}=min{57+∞; 22}=22 d_5,7⁷=min{d_5,7⁶+d_7,7⁶d_5,7⁶}=min{57+0; 57}=57 d_5,8⁷=min{d_5,7⁶+d_7,8⁶d_5,8⁶}=min{57+∞; ∞}=∞ d_6,1⁷=min{d_6,7⁶+d_7,1⁶d_6,1⁶}=min{35+∞; ∞}=∞ d_6,2⁷=min{d_6,7⁶+d_7,2⁶d_6,2⁶}=min{35+∞; ∞}=∞ d_6,3⁷=min{d_6,7⁶+d_7,3⁶d_6,3⁶}=min{35+∞; ∞}=∞ d_6,4⁷=min{d_6,7⁶+d_7,4⁶d_6,4⁶}=min{35+∞; ∞}=∞ d_6,5⁷=min{d_6,7⁶+d_7,5⁶d_6,5⁶}=min{35+∞; ∞}=∞ d_6,6⁷=min{d_6,7⁶+d_7,6⁶d_6,6⁶}=min{35+∞; 0}=0 d_6,7⁷=min{d_6,7⁶+d_7,7⁶d_6,7⁶}=min{35+0; 35}=35 d_6,8⁷=min{d_6,7⁶+d_7,8⁶d_6,8⁶}=min{35+∞; ∞}=∞ d_7,1⁷=min{d_7,7⁶+d_7,1⁶d_7,1⁶}=min{0+∞; ∞}=∞ d_7,2⁷=min{d_7,7⁶+d_7,2⁶d_7,2⁶}=min{0+∞; ∞}=∞ d_7,3⁷=min{d_7,7⁶+d_7,3⁶d_7,3⁶}=min{0+∞; ∞}=∞ d_7,4⁷=min{d_7,7⁶+d_7,4⁶d_7,4⁶}=min{0+∞; ∞}=∞ d_7,5⁷=min{d_7,7⁶+d_7,5⁶d_7,5⁶}=min{0+∞; ∞}=∞ d_7,6⁷=min{d_7,7⁶+d_7,6⁶d_7,6⁶}=min{0+∞; ∞}=∞ d_7,7⁷=min{d_7,7⁶+d_7,7⁶d_7,7⁶}=min{0+0; 0}=0 d_7,8⁷=min{d_7,7⁶+d_7,8⁶d_7,8⁶}=min{0+∞; ∞}=∞ d_8,1⁷=min{d_8,7⁶+d_7,1⁶d_8,1⁶}=min{∞+∞; ∞}=∞ d_8,2⁷=min{d_8,7⁶+d_7,2⁶d_8,2⁶}=min{∞+∞; ∞}=∞ d_8,3⁷=min{d_8,7⁶+d_7,3⁶d_8,3⁶}=min{∞+∞; ∞}=∞ d_8,4⁷=min{d_8,7⁶+d_7,4⁶d_8,4⁶}=min{∞+∞; ∞}=∞ d_8,5⁷=min{d_8,7⁶+d_7,5⁶d_8,5⁶}=min{∞+∞; ∞}=∞ d_8,6⁷=min{d_8,7⁶+d_7,6⁶d_8,6⁶}=min{∞+∞; ∞}=∞ d_8,7⁷=min{d_8,7⁶+d_7,7⁶d_8,7⁶}=min{∞+0; ∞}=∞ d_8,8⁷=min{d_8,7⁶+d_7,8⁶d_8,8⁶}=min{∞+∞; 0}=0 Представим матрицу D⁷, включив в нее рассчитанные элементы.

D7=	0	∞	∞	∞	∞	∞	∞	28
	14	0	∞	∞	31	53	88	42
	∞	∞	0	20	∞	9	38	35
	∞	∞	∞	0	∞	∞	18	15
	∞	∞	∞	∞	0	22	57	∞
	∞	∞	∞	∞	∞	0	35	∞
	∞	∞	∞	∞	∞	∞	0	∞
	∞	∞	∞	∞	∞	∞	∞	0

На основании матрицы D⁷, вычислим последовательно все элементы матрицы D⁸. Для этого мы используем рекуррентное соотношение d_i,j⁸=min{ d_i,8⁷+ d_8,j⁷; d_i,j⁷}. d_1,1⁸=min{d_1,8⁷+d_8,1⁷d_1,1⁷}=min{28+∞; 0}=0 d_1,2⁸=min{d_1,8⁷+d_8,2⁷d_1,2⁷}=min{28+∞; ∞}=∞ d_1,3⁸=min{d_1,8⁷+d_8,3⁷d_1,3⁷}=min{28+∞; ∞}=∞ d_1,4⁸=min{d_1,8⁷+d_8,4⁷d_1,4⁷}=min{28+∞; ∞}=∞ d_1,5⁸=min{d_1,8⁷+d_8,5⁷d_1,5⁷}=min{28+∞; ∞}=∞ d_1,6⁸=min{d_1,8⁷+d_8,6⁷d_1,6⁷}=min{28+∞; ∞}=∞ d_1,7⁸=min{d_1,8⁷+d_8,7⁷d_1,7⁷}=min{28+∞; ∞}=∞ d_1,8⁸=min{d_1,8⁷+d_8,8⁷d_1,8⁷}=min{28+0; 28}=28 d_2,1⁸=min{d_2,8⁷+d_8,1⁷d_2,1⁷}=min{42+∞; 14}=14 d_2,2⁸=min{d_2,8⁷+d_8,2⁷d_2,2⁷}=min{42+∞; 0}=0 d_2,3⁸=min{d_2,8⁷+d_8,3⁷d_2,3⁷}=min{42+∞; ∞}=∞ d_2,4⁸=min{d_2,8⁷+d_8,4⁷d_2,4⁷}=min{42+∞; ∞}=∞ d_2,5⁸=min{d_2,8⁷+d_8,5⁷d_2,5⁷}=min{42+∞; 31}=31 d_2,6⁸=min{d_2,8⁷+d_8,6⁷d_2,6⁷}=min{42+∞; 53}=53 d_2,7⁸=min{d_2,8⁷+d_8,7⁷d_2,7⁷}=min{42+∞; 88}=88 d_2,8⁸=min{d_2,8⁷+d_8,8⁷d_2,8⁷}=min{42+0; 42}=42 d_3,1⁸=min{d_3,8⁷+d_8,1⁷d_3,1⁷}=min{35+∞; ∞}=∞ d_3,2⁸=min{d_3,8⁷+d_8,2⁷d_3,2⁷}=min{35+∞; ∞}=∞ d_3,3⁸=min{d_3,8⁷+d_8,3⁷d_3,3⁷}=min{35+∞; 0}=0 d_3,4⁸=min{d_3,8⁷+d_8,4⁷d_3,4⁷}=min{35+∞; 20}=20 d_3,5⁸=min{d_3,8⁷+d_8,5⁷d_3,5⁷}=min{35+∞; ∞}=∞ d_3,6⁸=min{d_3,8⁷+d_8,6⁷d_3,6⁷}=min{35+∞; 9}=9 d_3,7⁸=min{d_3,8⁷+d_8,7⁷d_3,7⁷}=min{35+∞; 38}=38 d_3,8⁸=min{d_3,8⁷+d_8,8⁷d_3,8⁷}=min{35+0; 35}=35 d_4,1⁸=min{d_4,8⁷+d_8,1⁷d_4,1⁷}=min{15+∞; ∞}=∞ d_4,2⁸=min{d_4,8⁷+d_8,2⁷d_4,2⁷}=min{15+∞; ∞}=∞ d_4,3⁸=min{d_4,8⁷+d_8,3⁷d_4,3⁷}=min{15+∞; ∞}=∞ d_4,4⁸=min{d_4,8⁷+d_8,4⁷d_4,4⁷}=min{15+∞; 0}=0 d_4,5⁸=min{d_4,8⁷+d_8,5⁷d_4,5⁷}=min{15+∞; ∞}=∞ d_4,6⁸=min{d_4,8⁷+d_8,6⁷d_4,6⁷}=min{15+∞; ∞}=∞ d_4,7⁸=min{d_4,8⁷+d_8,7⁷d_4,7⁷}=min{15+∞; 18}=18 d_4,8⁸=min{d_4,8⁷+d_8,8⁷d_4,8⁷}=min{15+0; 15}=15 d_5,1⁸=min{d_5,8⁷+d_8,1⁷d_5,1⁷}=min{∞+∞; ∞}=∞ d_5,2⁸=min{d_5,8⁷+d_8,2⁷d_5,2⁷}=min{∞+∞; ∞}=∞ d_5,3⁸=min{d_5,8⁷+d_8,3⁷d_5,3⁷}=min{∞+∞; ∞}=∞ d_5,4⁸=min{d_5,8⁷+d_8,4⁷d_5,4⁷}=min{∞+∞; ∞}=∞ d_5,5⁸=min{d_5,8⁷+d_8,5⁷d_5,5⁷}=min{∞+∞; 0}=0 d_5,6⁸=min{d_5,8⁷+d_8,6⁷d_5,6⁷}=min{∞+∞; 22}=22 d_5,7⁸=min{d_5,8⁷+d_8,7⁷d_5,7⁷}=min{∞+∞; 57}=57 d_5,8⁸=min{d_5,8⁷+d_8,8⁷d_5,8⁷}=min{∞+0; ∞}=∞ d_6,1⁸=min{d_6,8⁷+d_8,1⁷d_6,1⁷}=min{∞+∞; ∞}=∞ d_6,2⁸=min{d_6,8⁷+d_8,2⁷d_6,2⁷}=min{∞+∞; ∞}=∞ d_6,3⁸=min{d_6,8⁷+d_8,3⁷d_6,3⁷}=min{∞+∞; ∞}=∞ d_6,4⁸=min{d_6,8⁷+d_8,4⁷d_6,4⁷}=min{∞+∞; ∞}=∞ d_6,5⁸=min{d_6,8⁷+d_8,5⁷d_6,5⁷}=min{∞+∞; ∞}=∞ d_6,6⁸=min{d_6,8⁷+d_8,6⁷d_6,6⁷}=min{∞+∞; 0}=0 d_6,7⁸=min{d_6,8⁷+d_8,7⁷d_6,7⁷}=min{∞+∞; 35}=35 d_6,8⁸=min{d_6,8⁷+d_8,8⁷d_6,8⁷}=min{∞+0; ∞}=∞ d_7,1⁸=min{d_7,8⁷+d_8,1⁷d_7,1⁷}=min{∞+∞; ∞}=∞ d_7,2⁸=min{d_7,8⁷+d_8,2⁷d_7,2⁷}=min{∞+∞; ∞}=∞ d_7,3⁸=min{d_7,8⁷+d_8,3⁷d_7,3⁷}=min{∞+∞; ∞}=∞ d_7,4⁸=min{d_7,8⁷+d_8,4⁷d_7,4⁷}=min{∞+∞; ∞}=∞ d_7,5⁸=min{d_7,8⁷+d_8,5⁷d_7,5⁷}=min{∞+∞; ∞}=∞ d_7,6⁸=min{d_7,8⁷+d_8,6⁷d_7,6⁷}=min{∞+∞; ∞}=∞ d_7,7⁸=min{d_7,8⁷+d_8,7⁷d_7,7⁷}=min{∞+∞; 0}=0 d_7,8⁸=min{d_7,8⁷+d_8,8⁷d_7,8⁷}=min{∞+0; ∞}=∞ d_8,1⁸=min{d_8,8⁷+d_8,1⁷d_8,1⁷}=min{0+∞; ∞}=∞ d_8,2⁸=min{d_8,8⁷+d_8,2⁷d_8,2⁷}=min{0+∞; ∞}=∞ d_8,3⁸=min{d_8,8⁷+d_8,3⁷d_8,3⁷}=min{0+∞; ∞}=∞ d_8,4⁸=min{d_8,8⁷+d_8,4⁷d_8,4⁷}=min{0+∞; ∞}=∞ d_8,5⁸=min{d_8,8⁷+d_8,5⁷d_8,5⁷}=min{0+∞; ∞}=∞ d_8,6⁸=min{d_8,8⁷+d_8,6⁷d_8,6⁷}=min{0+∞; ∞}=∞ d_8,7⁸=min{d_8,8⁷+d_8,7⁷d_8,7⁷}=min{0+∞; ∞}=∞ d_8,8⁸=min{d_8,8⁷+d_8,8⁷d_8,8⁷}=min{0+0; 0}=0 Представим матрицу D⁸, включив в нее рассчитанные элементы.

D8=	0	∞	∞	∞	∞	∞	∞	28
	14	0	∞	∞	31	53	88	42
	∞	∞	0	20	∞	9	38	35
	∞	∞	∞	0	∞	∞	18	15
	∞	∞	∞	∞	0	22	57	∞
	∞	∞	∞	∞	∞	0	35	∞
	∞	∞	∞	∞	∞	∞	0	∞
	∞	∞	∞	∞	∞	∞	∞	0

Висновок: я навчився застосовувати основні методи розробки алгоритмів