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

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

	1	2	3	4	5	6	7
1	INF	73	50	84	39	38	55
2	1	INF	35	70	84	64	8
3	37	64	INF	6	86	82	90
4	23	54	94	INF	93	30	13
5	48	11	50	31	INF	42	90
6	18	67	28	91	93	INF	22
7	32	89	10	17	80	76	INF

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

Мнимальные по строкам:38 1 6 13 11 18 10

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

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

Подсчитанные степени у нулей:
(1:5)=69
(1:6)=17
(2:1)=7
(3:4)=38
(4:7)=14
(5:2)=55
(6:1)=4
(7:3)=17

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

Максимумы по строкам:69 7 38 14 55 4 17

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

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

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

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

(1:5)

Поиск циклов

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

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

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

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

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	13	63	7
3	31	58	INF	0	10	76	84
4	10	41	81	INF	10	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	5	INF	4
7	22	79	0	7	0	66	INF

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

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

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

Максимумы по строкам:29 7 17 14 55 4 10

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

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

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

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

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	37	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

Поиск циклов

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

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

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

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

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	6	7
2	0	INF	34	69	46	7
3	31	58	INF	0	59	84
4	10	41	81	INF	0	0
5	INF	0	39	20	14	79
6	0	49	10	73	INF	4
7	22	79	0	7	49	INF

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

Подсчитанные степени у нулей:
(2:1)=7
(3:4)=38
(4:6)=14
(4:7)=4
(5:2)=55
(6:1)=4
(7:3)=17

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

Максимумы по строкам:7 38 14 55 4 17

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

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

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

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

	1	2	3	4	6	7
2	0	INF	34	69	46	7
3	31	58	INF	0	59	84
4	10	41	81	INF	0	0
5	INF	0	39	20	14	79
6	0	49	10	73	INF	4
7	22	79	0	7	49	INF

(5:2)

Поиск циклов

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

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

	1	2	3	4	6	7
2	0	INF	34	69	46	7
3	31	58	INF	0	59	84
4	10	41	81	INF	0	0
5	INF	INF	39	20	14	79
6	0	49	10	73	INF	4
7	22	79	0	7	49	INF

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

	1	2	3	4	6	7
2	0	INF	34	69	46	7
3	31	58	INF	0	59	84
4	10	41	81	INF	0	0
5	INF	INF	39	20	14	79
6	0	49	10	73	INF	4
7	22	79	0	7	49	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	6	7
2	0	INF	34	69	46	7
3	31	17	INF	0	59	84
4	10	0	81	INF	0	0
5	INF	INF	25	6	0	65
6	0	8	10	73	INF	4
7	22	38	0	7	49	INF

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

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

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

Максимумы по строкам:7 23 8 6 4 17

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

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

	1	2	3	4	6	7
2	0	INF	34	69	46	7
3	31	58	INF	0	59	84
4	10	41	81	INF	0	0
5	INF	0	39	20	14	79
6	0	49	10	73	INF	4
7	22	79	0	7	49	INF

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

	1	3	4	6	7
2	0	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	0	0
6	0	10	73	INF	4
7	22	0	7	49	INF

Поиск циклов

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

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

	1	3	4	6	7
2	0	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	0	0
6	0	10	73	INF	4
7	22	0	7	49	INF

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

	1	3	4	6	7
2	0	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	0	0
6	0	10	73	INF	4
7	22	0	7	49	INF

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

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

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

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

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

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

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

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

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

	1	3	4	6	7
2	0	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	0	0
6	0	10	73	INF	4
7	22	0	7	49	INF

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

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

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

Максимумы по строкам:7 38 46 4 17

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

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

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

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

	1	3	4	6	7
2	0	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	0	0
6	0	10	73	INF	4
7	22	0	7	49	INF

(4:6)

Поиск циклов

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

Поиск циклов

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

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

	1	3	4	6	7
2	INF	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	INF	0
6	0	10	73	INF	4
7	22	0	7	49	INF

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

	1	3	4	6	7
2	INF	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	INF	0
6	0	10	73	INF	4
7	22	0	7	49	INF

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

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

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

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

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

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

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

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

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

	1	3	4	6	7
2	INF	27	62	0	0
3	31	INF	0	20	84
4	10	81	INF	INF	0
6	0	10	73	INF	4
7	22	0	7	10	INF

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

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

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

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

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

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

	1	3	4	6	7
2	0	34	69	46	7
3	31	INF	0	59	84
4	10	81	INF	0	0
6	0	10	73	INF	4
7	22	0	7	49	INF

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

	1	3	4	7
2	0	34	69	7
3	31	INF	0	84
6	0	10	73	4
7	22	0	7	INF

Поиск циклов

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

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

	1	3	4	7
2	INF	34	69	7
3	31	INF	0	84
6	0	10	INF	4
7	22	0	7	INF

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

	1	3	4	7
2	INF	34	69	7
3	31	INF	0	84
6	0	10	INF	4
7	22	0	7	INF

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

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

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

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

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

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

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

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

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

	1	3	4	7
2	INF	27	62	0
3	31	INF	0	84
6	0	10	INF	4
7	22	0	7	INF

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

Подсчитанные степени у нулей:
(2:7)=31
(3:4)=38
(6:1)=26
(7:3)=17

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

Максимумы по строкам:31 38 26 17

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

Граница у несодержащего ребро (4,6):161 у содержащего122

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

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

	1	3	4	7
2	INF	27	62	0
3	31	INF	0	84
6	0	10	INF	4
7	22	0	7	INF

(3:4)

Поиск циклов

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

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

	1	3	4	7
2	INF	27	62	0
3	31	INF	INF	84
6	0	10	INF	4
7	22	0	7	INF

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

	1	3	4	7
2	INF	27	62	0
3	31	INF	INF	84
6	0	10	INF	4
7	22	0	7	INF

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

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

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

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

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

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

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

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

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

	1	3	4	7
2	INF	27	55	0
3	0	INF	INF	53
6	0	10	INF	4
7	22	0	0	INF

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

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

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

Максимумы по строкам:31 53 4 55

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

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

	1	3	4	7
2	INF	27	62	0
3	31	INF	0	84
6	0	10	INF	4
7	22	0	7	INF

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

	1	3	7
2	INF	27	0
6	0	10	4
7	22	0	INF

Поиск циклов

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

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

	1	3	7
2	INF	27	0
6	0	10	4
7	22	0	INF

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

	1	3	7
2	INF	27	0
6	0	10	4
7	22	0	INF

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

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

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

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

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

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

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

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

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

	1	3	7
2	INF	27	0
6	0	10	4
7	22	0	INF

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

Подсчитанные степени у нулей:
(2:7)=31
(6:1)=26
(7:3)=32

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

Максимумы по строкам:31 26 32

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

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

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

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

	1	3	7
2	INF	27	0
6	0	10	4
7	22	0	INF

(7:3)

Поиск циклов

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

Поиск циклов

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

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

	1	3	7
2	INF	27	0
6	0	INF	4
7	22	INF	INF

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

	1	3	7
2	INF	27	0
6	0	INF	4
7	22	INF	INF

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

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

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

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

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

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

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

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

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

	1	3	7
2	INF	0	0
6	0	INF	4
7	0	INF	INF

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

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

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

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

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

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

	1	3	7
2	INF	27	0
6	0	10	4
7	22	0	INF

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

	1	7
2	INF	0
6	0	4

Поиск циклов

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

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

	1	7
2	INF	0
6	0	4

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

	1	7
2	INF	0
6	0	4

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

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

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

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

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

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

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

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

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

	1	7
2	INF	0
6	0	4

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

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

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

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

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

Граница у несодержащего ребро (7,3):171 у содержащего122

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

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

	1	7
2	INF	0
6	0	4

(2:7)

Поиск циклов

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

Поиск циклов

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

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

	1	7
2	INF	INF
6	0	INF

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

	1	7
2	INF	INF
6	0	INF

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

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

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

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

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

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

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

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

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

	1	7
2	INF	INF
6	0	INF

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

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

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

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

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

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

	1	7
2	INF	0
6	0	4

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

	1
6	0

Поиск циклов

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

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

	1
6	0

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

	1
6	0

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

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

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

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

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

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

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

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

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

	1
6	0

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

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

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

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

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

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

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

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

	1
6	0

добавили в путь 6:1

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	73	50	84	39	38	55
2	1	INF	35	70	84	64	8
3	37	64	INF	6	86	82	90
4	23	54	94	INF	93	30	13
5	48	11	50	31	INF	42	90
6	18	67	28	91	93	INF	22
7	32	89	10	17	80	76	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	13	63	7
3	31	58	INF	0	10	76	84
4	10	41	81	INF	10	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	5	INF	4
7	22	79	0	7	0	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	37	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	5	6	7
1	INF	73	50	84	39	38	55
2	1	INF	35	70	84	64	8
3	37	64	INF	6	86	82	90
4	23	54	94	INF	93	30	13
5	48	11	50	31	INF	42	90
6	18	67	28	91	93	INF	22
7	32	89	10	17	80	76	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	13	63	7
3	31	58	INF	0	10	76	84
4	10	41	81	INF	10	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	5	INF	4
7	22	79	0	7	0	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	37	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	73	50	84	39	38	55
2	1	INF	35	70	84	64	8
3	37	64	INF	6	86	82	90
4	23	54	94	INF	93	30	13
5	48	11	50	31	INF	42	90
6	18	67	28	91	93	INF	22
7	32	89	10	17	80	76	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	INF	0	17
2	0	INF	34	69	13	63	7
3	31	58	INF	0	10	76	84
4	10	41	81	INF	10	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	5	INF	4
7	22	79	0	7	0	66	INF

	1	2	3	4	5	6	7
1	INF	35	12	46	0	0	17
2	0	INF	34	69	82	63	7
3	31	58	INF	0	79	76	84
4	10	41	81	INF	79	17	0
5	37	0	39	20	INF	31	79
6	0	49	10	73	74	INF	4
7	22	79	0	7	69	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	37	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF

	1	2	3	4	6	7
2	0	INF	34	69	63	7
3	31	58	INF	0	76	84
4	10	41	81	INF	17	0
5	INF	0	39	20	31	79
6	0	49	10	73	INF	4
7	22	79	0	7	66	INF