Метод ветвей и границ

Вычитание минимумов по строке

	1	2	3	4	5	6	7
1	INF	17	45	83	88	50	7
2	91	INF	9	36	81	84	98
3	13	85	INF	11	83	83	75
4	23	3	24	INF	47	93	92
5	20	93	88	81	INF	80	19
6	4	44	22	38	1	INF	82
7	13	43	49	74	42	16	INF

Нахождение минимальных по строкам

Мнимальные по строкам:7 9 11 3 19 1 13

Почти новая мин граница 63

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 3 0

Новая мин граница 66

Результат вычитания минимумов по столбцам

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(2:3)=48
(3:4)=29
(4:2)=30
(5:7)=1
(6:5)=32
(7:1)=1
(7:6)=40

Конец подсчета штрафов у нулей

Максимумы по строкам:10 48 29 30 1 32 40

Максимальная степень 0 находятся на позициях (2:3)

Нули на предыдущих этапах:(2:3)

Начинаем разделение

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

(2:3)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (2,3)

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

Вычитание минимумов по строке

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 27 0 0 0 0 0

Почти новая мин граница 93

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 21 0 0 0 0

Новая мин граница 114

Результат вычитания минимумов по столбцам

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	0	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(2:4)=45
(3:4)=2
(4:2)=10
(4:3)=0
(5:7)=1
(6:3)=0
(6:5)=29
(7:1)=1
(7:6)=40

Конец подсчета штрафов у нулей

Максимумы по строкам:10 45 2 10 1 29 40

Максимальная степень 0 находятся на позициях (2:4)

Удаление из матрицы 2:3

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

Результат удаления из матрицы 2:3

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	74	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (2,3)

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

Вычитание минимумов по строке

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0 0

Почти новая мин граница 66

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 0

Новая мин граница 66

Результат вычитания минимумов по столбцам

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(3:4)=39
(4:2)=30
(5:7)=1
(6:5)=32
(7:1)=1
(7:6)=40

Конец подсчета штрафов у нулей

Максимумы по строкам:10 39 30 1 32 40

Максимальная степень 0 находятся на позициях (7:6)

Граница у несодержащего ребро (2,3):114 у содержащего66

Нули на предыдущих этапах:(7:6) (2:3)

Начинаем разделение

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

(7:6)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (7,6)

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

Вычитание минимумов по строке

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0 0

Почти новая мин граница 66

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 40 0

Новая мин граница 106

Результат вычитания минимумов по столбцам

	1	2	4	5	6	7
1	INF	10	76	81	0	0
3	2	INF	0	72	29	64
4	20	0	INF	44	47	89
5	1	74	62	INF	18	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:6)=18
(1:7)=0
(3:4)=39
(4:2)=30
(5:7)=1
(6:5)=32
(7:1)=30

Конец подсчета штрафов у нулей

Максимумы по строкам:18 39 30 1 32 30

Максимальная степень 0 находятся на позициях (3:4)

Удаление из матрицы 7:6

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

Результат удаления из матрицы 7:6

	1	2	4	5	7
1	INF	10	76	81	0
3	2	INF	0	72	64
4	20	0	INF	44	89
5	1	74	62	INF	0
6	3	43	37	0	81

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (7,6)

	1	2	4	5	7
1	INF	10	76	81	0
3	2	INF	0	72	64
4	20	0	INF	44	89
5	1	74	62	INF	0
6	3	43	37	0	INF

Вычитание минимумов по строке

	1	2	4	5	7
1	INF	10	76	81	0
3	2	INF	0	72	64
4	20	0	INF	44	89
5	1	74	62	INF	0
6	3	43	37	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0

Почти новая мин граница 66

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:1 0 0 0 0

Новая мин граница 67

Результат вычитания минимумов по столбцам

	1	2	4	5	7
1	INF	10	76	81	0
3	1	INF	0	72	64
4	19	0	INF	44	89
5	0	74	62	INF	0
6	2	43	37	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(3:4)=38
(4:2)=29
(5:1)=1
(5:7)=0
(6:5)=46

Конец подсчета штрафов у нулей

Максимумы по строкам:10 38 29 1 46

Максимальная степень 0 находятся на позициях (6:5)

Граница у несодержащего ребро (7,6):106 у содержащего67

Нули на предыдущих этапах:(6:5) (7:6) (2:3)

Начинаем разделение

	1	2	4	5	7
1	INF	10	76	81	0
3	1	INF	0	72	64
4	19	0	INF	44	89
5	0	74	62	INF	0
6	2	43	37	0	INF

(6:5)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (6,5)

	1	2	4	5	7
1	INF	10	76	81	0
3	1	INF	0	72	64
4	19	0	INF	44	89
5	0	74	62	INF	0
6	2	43	37	INF	INF

Вычитание минимумов по строке

	1	2	4	5	7
1	INF	10	76	81	0
3	1	INF	0	72	64
4	19	0	INF	44	89
5	0	74	62	INF	0
6	2	43	37	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 2

Почти новая мин граница 69

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 44 0

Новая мин граница 113

Результат вычитания минимумов по столбцам

	1	2	4	5	7
1	INF	10	76	37	0
3	1	INF	0	28	64
4	19	0	INF	0	89
5	0	74	62	INF	0
6	0	41	35	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(3:4)=36
(4:2)=10
(4:5)=28
(5:1)=0
(5:7)=0
(6:1)=35

Конец подсчета штрафов у нулей

Максимумы по строкам:10 36 28 0 35

Максимальная степень 0 находятся на позициях (3:4)

Удаление из матрицы 6:5

	1	2	4	5	7
1	INF	10	76	81	0
3	1	INF	0	72	64
4	19	0	INF	44	89
5	0	74	62	INF	0
6	2	43	37	0	INF

Результат удаления из матрицы 6:5

	1	2	4	7
1	INF	10	76	0
3	1	INF	0	64
4	19	0	INF	89
5	0	74	62	0

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (6,5)

	1	2	4	7
1	INF	10	76	0
3	1	INF	0	64
4	19	0	INF	89
5	0	74	62	0

Вычитание минимумов по строке

	1	2	4	7
1	INF	10	76	0
3	1	INF	0	64
4	19	0	INF	89
5	0	74	62	0

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0

Почти новая мин граница 67

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 67

Результат вычитания минимумов по столбцам

	1	2	4	7
1	INF	10	76	0
3	1	INF	0	64
4	19	0	INF	89
5	0	74	62	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(3:4)=63
(4:2)=29
(5:1)=1
(5:7)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:10 63 29 1

Максимальная степень 0 находятся на позициях (3:4)

Граница у несодержащего ребро (6,5):113 у содержащего67

Нули на предыдущих этапах:(3:4) (6:5) (7:6) (2:3)

Начинаем разделение

	1	2	4	7
1	INF	10	76	0
3	1	INF	0	64
4	19	0	INF	89
5	0	74	62	0

(3:4)

Поиск циклов

Цикл найден. уничтожен [7][5]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (3,4)

	1	2	4	7
1	INF	10	76	0
3	1	INF	INF	64
4	19	0	INF	89
5	0	74	62	INF

Вычитание минимумов по строке

	1	2	4	7
1	INF	10	76	0
3	1	INF	INF	64
4	19	0	INF	89
5	0	74	62	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 1 0 0

Почти новая мин граница 68

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 62 0

Новая мин граница 130

Результат вычитания минимумов по столбцам

	1	2	4	7
1	INF	10	14	0
3	0	INF	INF	63
4	19	0	INF	89
5	0	74	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=73
(3:1)=63
(4:2)=29
(5:1)=0
(5:4)=14

Конец подсчета штрафов у нулей

Максимумы по строкам:73 63 29 14

Максимальная степень 0 находятся на позициях (1:7)

Удаление из матрицы 3:4

	1	2	4	7
1	INF	10	76	0
3	1	INF	0	64
4	19	0	INF	89
5	0	74	62	0

Результат удаления из матрицы 3:4

	1	2	7
1	INF	10	0
4	19	0	89
5	0	74	0

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (3,4)

	1	2	7
1	INF	10	0
4	19	0	89
5	0	74	INF

Вычитание минимумов по строке

	1	2	7
1	INF	10	0
4	19	0	89
5	0	74	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0

Почти новая мин граница 67

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0

Новая мин граница 67

Результат вычитания минимумов по столбцам

	1	2	7
1	INF	10	0
4	19	0	89
5	0	74	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=99
(4:2)=29
(5:1)=93

Конец подсчета штрафов у нулей

Максимумы по строкам:99 29 93

Максимальная степень 0 находятся на позициях (1:7)

Граница у несодержащего ребро (3,4):130 у содержащего67

Нули на предыдущих этапах:(1:7) (3:4) (6:5) (7:6) (2:3)

Начинаем разделение

	1	2	7
1	INF	10	0
4	19	0	89
5	0	74	INF

(1:7)

Поиск циклов

Цикл найден. уничтожен [2][4]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (1,7)

	1	2	7
1	INF	10	INF
4	19	INF	89
5	0	74	INF

Вычитание минимумов по строке

	1	2	7
1	INF	10	INF
4	19	INF	89
5	0	74	INF

Нахождение минимальных по строкам

Мнимальные по строкам:10 19 0

Почти новая мин граница 96

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 70

Новая мин граница 166

Результат вычитания минимумов по столбцам

	1	2	7
1	INF	0	INF
4	0	INF	0
5	0	74	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=74
(4:1)=0
(4:7)=0
(5:1)=74

Конец подсчета штрафов у нулей

Максимумы по строкам:74 0 74

Максимальная степень 0 находятся на позициях (1:2)

Удаление из матрицы 1:7

	1	2	7
1	INF	10	0
4	19	0	89
5	0	74	INF

Результат удаления из матрицы 1:7

	1	2
4	19	0
5	0	74

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (1,7)

	1	2
4	19	INF
5	0	74

Вычитание минимумов по строке

	1	2
4	19	INF
5	0	74

Нахождение минимальных по строкам

Мнимальные по строкам:19 0

Почти новая мин граница 86

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 74

Новая мин граница 160

Результат вычитания минимумов по столбцам

	1	2
4	0	INF
5	0	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(4:1)=0
(5:1)=0
(5:2)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0 0

Максимальная степень 0 находятся на позициях (4:1)

Граница у несодержащего ребро (1,7):166 у содержащего160

Нули на предыдущих этапах:(3:4) (7:6) (2:3)

Начинаем разделение

	1	2	4	5	6	7
1	INF	10	76	81	0	0
3	2	INF	0	72	29	64
4	20	0	INF	44	47	89
5	1	74	62	INF	18	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

(3:4)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (3,4)

	1	2	4	5	6	7
1	INF	10	76	81	0	0
3	2	INF	INF	72	29	64
4	20	0	INF	44	47	89
5	1	74	62	INF	18	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

Вычитание минимумов по строке

	1	2	4	5	6	7
1	INF	10	76	81	0	0
3	2	INF	INF	72	29	64
4	20	0	INF	44	47	89
5	1	74	62	INF	18	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 2 0 0 0 0

Почти новая мин граница 108

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 37 0 0 0

Новая мин граница 145

Результат вычитания минимумов по столбцам

	1	2	4	5	6	7
1	INF	10	39	81	0	0
3	0	INF	INF	70	27	62
4	20	0	INF	44	47	89
5	1	74	25	INF	18	0
6	3	43	0	0	INF	81
7	0	30	24	29	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:6)=18
(1:7)=0
(3:1)=27
(4:2)=30
(5:7)=1
(6:4)=24
(6:5)=29
(7:1)=24

Конец подсчета штрафов у нулей

Максимумы по строкам:18 27 30 1 29 24

Максимальная степень 0 находятся на позициях (4:2)

Удаление из матрицы 3:4

	1	2	4	5	6	7
1	INF	10	76	81	0	0
3	2	INF	0	72	29	64
4	20	0	INF	44	47	89
5	1	74	62	INF	18	0
6	3	43	37	0	INF	81
7	0	30	61	29	INF	INF

Результат удаления из матрицы 3:4

	1	2	5	6	7
1	INF	10	81	0	0
4	20	0	44	47	89
5	1	74	INF	18	0
6	3	43	0	INF	81
7	0	30	29	INF	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (3,4)

	1	2	5	6	7
1	INF	10	81	0	0
4	20	0	44	47	89
5	1	74	INF	18	0
6	3	43	0	INF	81
7	0	30	29	INF	INF

Вычитание минимумов по строке

	1	2	5	6	7
1	INF	10	81	0	0
4	20	0	44	47	89
5	1	74	INF	18	0
6	3	43	0	INF	81
7	0	30	29	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0

Почти новая мин граница 106

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0

Новая мин граница 106

Результат вычитания минимумов по столбцам

	1	2	5	6	7
1	INF	10	81	0	0
4	20	0	44	47	89
5	1	74	INF	18	0
6	3	43	0	INF	81
7	0	30	29	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:6)=18
(1:7)=0
(4:2)=30
(5:7)=1
(6:5)=32
(7:1)=30

Конец подсчета штрафов у нулей

Максимумы по строкам:18 30 1 32 30

Максимальная степень 0 находятся на позициях (6:5)

Граница у несодержащего ребро (3,4):145 у содержащего106

Нули на предыдущих этапах:(6:5) (3:4) (7:6) (2:3)

Начинаем разделение

	1	2	5	6	7
1	INF	10	81	0	0
4	20	0	44	47	89
5	1	74	INF	18	0
6	3	43	0	INF	81
7	0	30	29	INF	INF

(6:5)

Поиск циклов

Цикл найден. уничтожен [2][4]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (6,5)

	1	2	5	6	7
1	INF	10	81	0	0
4	20	INF	44	47	89
5	1	74	INF	18	0
6	3	43	INF	INF	81
7	0	30	29	INF	INF

Вычитание минимумов по строке

	1	2	5	6	7
1	INF	10	81	0	0
4	20	INF	44	47	89
5	1	74	INF	18	0
6	3	43	INF	INF	81
7	0	30	29	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 20 0 3 0

Почти новая мин граница 129

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 10 24 0 0

Новая мин граница 163

Результат вычитания минимумов по столбцам

	1	2	5	6	7
1	INF	0	57	0	0
4	0	INF	0	27	69
5	1	64	INF	18	0
6	0	30	INF	INF	78
7	0	20	5	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=20
(1:6)=18
(1:7)=0
(4:1)=0
(4:5)=5
(5:7)=1
(6:1)=30
(7:1)=5

Конец подсчета штрафов у нулей

Максимумы по строкам:20 5 1 30 5

Максимальная степень 0 находятся на позициях (6:1)

Удаление из матрицы 6:5

	1	2	5	6	7
1	INF	10	81	0	0
4	20	0	44	47	89
5	1	74	INF	18	0
6	3	43	0	INF	81
7	0	30	29	INF	INF

Результат удаления из матрицы 6:5

	1	2	6	7
1	INF	10	0	0
4	20	0	47	89
5	1	74	18	0
7	0	30	INF	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (6,5)

	1	2	6	7
1	INF	10	0	0
4	20	INF	47	89
5	1	74	INF	0
7	0	30	INF	INF

Вычитание минимумов по строке

	1	2	6	7
1	INF	10	0	0
4	20	INF	47	89
5	1	74	INF	0
7	0	30	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 20 0 0

Почти новая мин граница 126

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 10 0 0

Новая мин граница 136

Результат вычитания минимумов по столбцам

	1	2	6	7
1	INF	0	0	0
4	0	INF	27	69
5	1	64	INF	0
7	0	20	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=20
(1:6)=27
(1:7)=0
(4:1)=27
(5:7)=1
(7:1)=20

Конец подсчета штрафов у нулей

Максимумы по строкам:27 27 1 20

Максимальная степень 0 находятся на позициях (1:6)

Граница у несодержащего ребро (6,5):163 у содержащего136

Нули на предыдущих этапах:(3:4) (6:5) (7:6) (2:3)

Начинаем разделение

	1	2	4	5	7
1	INF	10	76	37	0
3	1	INF	0	28	64
4	19	0	INF	0	89
5	0	74	62	INF	0
6	0	41	35	INF	INF

(3:4)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (3,4)

	1	2	4	5	7
1	INF	10	76	37	0
3	1	INF	INF	28	64
4	19	0	INF	0	89
5	0	74	62	INF	0
6	0	41	35	INF	INF

Вычитание минимумов по строке

	1	2	4	5	7
1	INF	10	76	37	0
3	1	INF	INF	28	64
4	19	0	INF	0	89
5	0	74	62	INF	0
6	0	41	35	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 1 0 0 0

Почти новая мин граница 114

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 35 0 0

Новая мин граница 149

Результат вычитания минимумов по столбцам

	1	2	4	5	7
1	INF	10	41	37	0
3	0	INF	INF	27	63
4	19	0	INF	0	89
5	0	74	27	INF	0
6	0	41	0	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(3:1)=27
(4:2)=10
(4:5)=27
(5:1)=0
(5:7)=0
(6:1)=0
(6:4)=27

Конец подсчета штрафов у нулей

Максимумы по строкам:10 27 27 0 27

Максимальная степень 0 находятся на позициях (3:1)

Удаление из матрицы 3:4

	1	2	4	5	7
1	INF	10	76	37	0
3	1	INF	0	28	64
4	19	0	INF	0	89
5	0	74	62	INF	0
6	0	41	35	INF	INF

Результат удаления из матрицы 3:4

	1	2	5	7
1	INF	10	37	0
4	19	0	0	89
5	0	74	INF	0
6	0	41	INF	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (3,4)

	1	2	5	7
1	INF	10	37	0
4	19	0	0	89
5	0	74	INF	0
6	0	41	INF	INF

Вычитание минимумов по строке

	1	2	5	7
1	INF	10	37	0
4	19	0	0	89
5	0	74	INF	0
6	0	41	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0

Почти новая мин граница 113

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 113

Результат вычитания минимумов по столбцам

	1	2	5	7
1	INF	10	37	0
4	19	0	0	89
5	0	74	INF	0
6	0	41	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(4:2)=10
(4:5)=37
(5:1)=0
(5:7)=0
(6:1)=41

Конец подсчета штрафов у нулей

Максимумы по строкам:10 37 0 41

Максимальная степень 0 находятся на позициях (6:1)

Граница у несодержащего ребро (3,4):149 у содержащего113

Нули на предыдущих этапах:(6:1) (3:4) (6:5) (7:6) (2:3)

Начинаем разделение

	1	2	5	7
1	INF	10	37	0
4	19	0	0	89
5	0	74	INF	0
6	0	41	INF	INF

(6:1)

Поиск циклов

Цикл найден. уничтожен [2][4]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (6,1)

	1	2	5	7
1	INF	10	37	0
4	19	INF	0	89
5	0	74	INF	0
6	INF	41	INF	INF

Вычитание минимумов по строке

	1	2	5	7
1	INF	10	37	0
4	19	INF	0	89
5	0	74	INF	0
6	INF	41	INF	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 41

Почти новая мин граница 154

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 154

Результат вычитания минимумов по столбцам

	1	2	5	7
1	INF	10	37	0
4	19	INF	0	89
5	0	74	INF	0
6	INF	0	INF	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(4:5)=56
(5:1)=19
(5:7)=0
(6:2)=10

Конец подсчета штрафов у нулей

Максимумы по строкам:10 56 19 10

Максимальная степень 0 находятся на позициях (4:5)

Удаление из матрицы 6:1

	1	2	5	7
1	INF	10	37	0
4	19	0	0	89
5	0	74	INF	0
6	0	41	INF	INF

Результат удаления из матрицы 6:1

	2	5	7
1	10	37	0
4	0	0	89
5	74	INF	0

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (6,1)

	2	5	7
1	10	37	0
4	INF	0	89
5	74	INF	0

Вычитание минимумов по строке

	2	5	7
1	10	37	0
4	INF	0	89
5	74	INF	0

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0

Почти новая мин граница 113

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:10 0 0

Новая мин граница 123

Результат вычитания минимумов по столбцам

	2	5	7
1	0	37	0
4	INF	0	89
5	64	INF	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=64
(1:7)=0
(4:5)=126
(5:7)=64

Конец подсчета штрафов у нулей

Максимумы по строкам:64 126 64

Максимальная степень 0 находятся на позициях (4:5)

Граница у несодержащего ребро (6,1):154 у содержащего123

Нули на предыдущих этапах:(2:4) (2:3)

Начинаем разделение

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	0	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

(2:4)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (2,4)

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	INF	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

Вычитание минимумов по строке

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	INF	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 45 0 0 0 0 0

Почти новая мин граница 159

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 0 0

Новая мин граница 159

Результат вычитания минимумов по столбцам

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	10	INF	INF	INF	0	0	17
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:7)=10
(2:5)=0
(2:6)=0
(3:4)=39
(4:2)=10
(4:3)=0
(5:7)=1
(6:3)=0
(6:5)=0
(7:1)=1
(7:6)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:10 0 39 10 1 0 1

Максимальная степень 0 находятся на позициях (3:4)

Удаление из матрицы 2:4

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	0	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

Результат удаления из матрицы 2:4

	1	2	3	5	6	7
1	INF	10	17	81	40	0
3	2	74	INF	72	69	64
4	20	0	0	44	87	89
5	1	74	48	INF	58	0
6	3	43	0	0	INF	81
7	0	30	15	29	0	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (2,4)

	1	2	3	5	6	7
1	INF	10	17	81	40	0
3	2	74	INF	72	69	64
4	20	INF	0	44	87	89
5	1	74	48	INF	58	0
6	3	43	0	0	INF	81
7	0	30	15	29	0	INF

Вычитание минимумов по строке

	1	2	3	5	6	7
1	INF	10	17	81	40	0
3	2	74	INF	72	69	64
4	20	INF	0	44	87	89
5	1	74	48	INF	58	0
6	3	43	0	0	INF	81
7	0	30	15	29	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 2 0 0 0 0

Почти новая мин граница 116

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 10 0 0 0 0

Новая мин граница 126

Результат вычитания минимумов по столбцам

	1	2	3	5	6	7
1	INF	0	17	81	40	0
3	0	62	INF	70	67	62
4	20	INF	0	44	87	89
5	1	64	48	INF	58	0
6	3	33	0	0	INF	81
7	0	20	15	29	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=20
(1:7)=0
(3:1)=62
(4:3)=20
(5:7)=1
(6:3)=0
(6:5)=29
(7:1)=0
(7:6)=40

Конец подсчета штрафов у нулей

Максимумы по строкам:20 62 20 1 29 40

Максимальная степень 0 находятся на позициях (3:1)

Граница у несодержащего ребро (2,4):159 у содержащего126

Нули на предыдущих этапах:(4:5) (6:1) (3:4) (6:5) (7:6) (2:3)

Начинаем разделение

	2	5	7
1	0	37	0
4	INF	0	89
5	64	INF	0

(4:5)

Поиск циклов

Цикл найден. уничтожен [7][1]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (4,5)

	2	5	7
1	0	37	INF
4	INF	INF	89
5	64	INF	0

Вычитание минимумов по строке

	2	5	7
1	0	37	INF
4	INF	INF	89
5	64	INF	0

Нахождение минимальных по строкам

Мнимальные по строкам:0 89 0

Почти новая мин граница 212

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 37 0

Новая мин граница 249

Результат вычитания минимумов по столбцам

	2	5	7
1	0	0	INF
4	INF	INF	0
5	64	INF	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=64
(1:5)=0
(4:7)=0
(5:7)=64

Конец подсчета штрафов у нулей

Максимумы по строкам:64 0 64

Максимальная степень 0 находятся на позициях (1:2)

Удаление из матрицы 4:5

	2	5	7
1	0	37	0
4	INF	0	89
5	64	INF	0

Результат удаления из матрицы 4:5

	2	7
1	0	0
5	64	0

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (4,5)

	2	7
1	0	INF
5	64	0

Вычитание минимумов по строке

	2	7
1	0	INF
5	64	0

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 123

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 123

Результат вычитания минимумов по столбцам

	2	7
1	0	INF
5	64	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=64
(5:7)=64

Конец подсчета штрафов у нулей

Максимумы по строкам:64 64

Максимальная степень 0 находятся на позициях (1:2)

Граница у несодержащего ребро (4,5):249 у содержащего123

Нули на предыдущих этапах:(1:2) (4:5) (6:1) (3:4) (6:5) (7:6) (2:3)

Начинаем разделение

	2	7
1	0	INF
5	64	0

(1:2)

Поиск циклов

Цикл найден. уничтожен [2][5]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (1,2)

	2	7
1	INF	INF
5	INF	0

Вычитание минимумов по строке

	2	7
1	INF	INF
5	INF	0

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 123

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 123

Результат вычитания минимумов по столбцам

	2	7
1	INF	INF
5	INF	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(5:7)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0

Максимальная степень 0 находятся на позициях (5:7)

Удаление из матрицы 1:2

	2	7
1	0	INF
5	64	0

Результат удаления из матрицы 1:2

	7
5	0

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (1,2)

	7
5	0

Вычитание минимумов по строке

	7
5	0

Нахождение минимальных по строкам

Мнимальные по строкам:0

Почти новая мин граница 123

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0

Новая мин граница 123

Результат вычитания минимумов по столбцам

	7
5	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(5:7)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0

Максимальная степень 0 находятся на позициях (5:7)

Граница у несодержащего ребро (1,2):123 у содержащего123

Нули на предыдущих этапах:(5:7) (1:2) (4:5) (6:1) (3:4) (6:5) (7:6) (2:3)

В таблице всего один элемент

	7
5	0

добавили в путь 5:7

Нули на предыдущих этапах:(5:7) (1:2) (4:5) (6:1) (3:4) (6:5) (7:6) (2:3)

Метод ветвей и границ

Примеры из веба для сверки ответов:

Таблица длин маршрутов

Легенда узла: _{Номер шага обработки}(Строка:Колонка)_{Стоимость}

(Для подбробного решения выберите нужный этап на дереве)

Ответ: путь:1=>2=>3=>4=>5=>7=>6=>1 длина: 123

	1	2	3	4	5	6	7
1	INF	17	45	83	88	50	7
2	91	INF	9	36	81	84	98
3	13	85	INF	11	83	83	75
4	23	3	24	INF	47	93	92
5	20	93	88	81	INF	80	19
6	4	44	22	38	1	INF	82
7	13	43	49	74	42	16	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	0	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	74	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	17	45	83	88	50	7
2	91	INF	9	36	81	84	98
3	13	85	INF	11	83	83	75
4	23	3	24	INF	47	93	92
5	20	93	88	81	INF	80	19
6	4	44	22	38	1	INF	82
7	13	43	49	74	42	16	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	0	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	74	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

Метод ветвей и границ

Примеры из веба для сверки ответов:

Таблица длин маршрутов

Легенда узла: Номер шага обработки(Строка:Колонка)Стоимость

(Для подбробного решения выберите нужный этап на дереве)

Ответ: путь:1=>2=>3=>4=>5=>7=>6=>1 длина: 123

Легенда узла: _{Номер шага обработки}(Строка:Колонка)_{Стоимость}

	1	2	3	4	5	6	7
1	INF	17	45	83	88	50	7
2	91	INF	9	36	81	84	98
3	13	85	INF	11	83	83	75
4	23	3	24	INF	47	93	92
5	20	93	88	81	INF	80	19
6	4	44	22	38	1	INF	82
7	13	43	49	74	42	16	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	INF	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	17	76	81	40	0
2	55	INF	INF	0	45	45	62
3	2	74	INF	0	72	69	64
4	20	0	0	INF	44	87	89
5	1	74	48	62	INF	58	0
6	3	43	0	37	0	INF	81
7	0	30	15	61	29	0	INF

	1	2	3	4	5	6	7
1	INF	10	38	76	81	40	0
2	82	INF	0	27	72	72	89
3	2	74	INF	0	72	69	64
4	20	0	21	INF	44	87	89
5	1	74	69	62	INF	58	0
6	3	43	21	37	0	INF	81
7	0	30	36	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	74	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF

	1	2	4	5	6	7
1	INF	10	76	81	40	0
3	2	INF	0	72	69	64
4	20	0	INF	44	87	89
5	1	74	62	INF	58	0
6	3	43	37	0	INF	81
7	0	30	61	29	0	INF