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

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

	1	2	3	4	5	6	7
1	INF	75	18	95	79	29	98
2	5	INF	81	30	0	59	67
3	90	18	INF	65	89	81	19
4	69	18	6	INF	32	6	67
5	59	24	94	20	INF	5	61
6	76	16	81	16	43	INF	34
7	39	79	27	20	22	97	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

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

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

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

Максимумы по строкам:11 14 17 0 15 0 2

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

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

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

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

(3:7)

Поиск циклов

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

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

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

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

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	62
2	0	INF	81	30	0	59	49
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	43
5	49	19	89	15	INF	0	38
6	55	0	65	0	27	INF	0
7	14	59	7	0	2	77	INF

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

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

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

Максимумы по строкам:11 14 47 0 15 38 2

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

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

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	7	0	2	77

Поиск циклов

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

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

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

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

Максимумы по строкам:11 14 0 15 12 2

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

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

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

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

(5:6)

Поиск циклов

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

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	INF
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	INF
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	34	4	74	0	INF	INF
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

	1	2	3	4	5
1	INF	57	0	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	27
7	14	59	INF	0	2

Поиск циклов

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

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

	1	2	3	4	5
1	INF	57	0	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

	1	2	3	4	5
1	INF	57	0	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

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

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

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

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

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

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

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

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

	1	2	3	4	5
1	INF	57	0	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

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

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

Максимумы по строкам:57 14 12 12 2

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

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

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

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

	1	2	3	4	5
1	INF	57	0	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

(1:3)

Поиск циклов

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

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

	1	2	3	4	5
1	INF	57	INF	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

	1	2	3	4	5
1	INF	57	INF	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

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

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

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

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

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

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

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

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

	1	2	3	4	5
1	INF	0	INF	20	4
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

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

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

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

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

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

	1	2	3	4	5
1	INF	57	0	77	61
2	0	INF	81	30	0
4	58	12	0	INF	26
6	55	0	65	0	INF
7	14	59	INF	0	2

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

	1	2	4	5
2	0	INF	30	0
4	58	12	INF	26
6	55	0	0	INF
7	14	59	0	2

Поиск циклов

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

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

	1	2	4	5
2	0	INF	30	0
4	58	12	INF	26
6	55	0	0	INF
7	14	59	0	2

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

	1	2	4	5
2	0	INF	30	0
4	58	12	INF	26
6	55	0	0	INF
7	14	59	0	2

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

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

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

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

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

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

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

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

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

	1	2	4	5
2	0	INF	30	0
4	46	0	INF	14
6	55	0	0	INF
7	14	59	0	2

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

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

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

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

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

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

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

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

	1	2	4	5
2	0	INF	30	0
4	46	0	INF	14
6	55	0	0	INF
7	14	59	0	2

(2:1)

Поиск циклов

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

Поиск циклов

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

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

	1	2	4	5
2	INF	INF	30	0
4	46	0	INF	14
6	55	0	0	INF
7	INF	59	0	2

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

	1	2	4	5
2	INF	INF	30	0
4	46	0	INF	14
6	55	0	0	INF
7	INF	59	0	2

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

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

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

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

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

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

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

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

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

	1	2	4	5
2	INF	INF	30	0
4	0	0	INF	14
6	9	0	0	INF
7	INF	59	0	2

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

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

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

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

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

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

	1	2	4	5
2	0	INF	30	0
4	46	0	INF	14
6	55	0	0	INF
7	14	59	0	2

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

	2	4	5
4	0	INF	14
6	0	0	INF
7	59	0	2

Поиск циклов

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

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

	2	4	5
4	0	INF	14
6	0	0	INF
7	59	0	2

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

	2	4	5
4	0	INF	14
6	0	0	INF
7	59	0	2

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

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

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

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

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

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

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

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

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

	2	4	5
4	0	INF	12
6	0	0	INF
7	59	0	0

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

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

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

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

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

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

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

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

	2	4	5
4	0	INF	12
6	0	0	INF
7	59	0	0

(4:2)

Поиск циклов

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

Поиск циклов

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

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

	2	4	5
4	INF	INF	12
6	0	0	INF
7	INF	0	0

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

	2	4	5
4	INF	INF	12
6	0	0	INF
7	INF	0	0

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

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

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

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

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

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

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

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

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

	2	4	5
4	INF	INF	0
6	0	0	INF
7	INF	0	0

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

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

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

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

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

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

	2	4	5
4	0	INF	12
6	0	0	INF
7	59	0	0

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

	4	5
6	0	INF
7	0	0

Поиск циклов

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

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

	4	5
6	0	INF
7	0	0

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

	4	5
6	0	INF
7	0	0

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

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

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

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

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

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

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

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

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

	4	5
6	0	INF
7	0	0

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

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

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

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

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

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

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

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

	4	5
6	0	INF
7	0	0

(6:4)

Поиск циклов

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

Поиск циклов

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

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

	4	5
6	INF	INF
7	INF	0

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

	4	5
6	INF	INF
7	INF	0

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

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

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

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

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

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

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

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

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

	4	5
6	INF	INF
7	INF	0

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

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

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

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

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

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

	4	5
6	0	INF
7	0	0

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

	5
7	0

Поиск циклов

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

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

	5
7	0

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

	5
7	0

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

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

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

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

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

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

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

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

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

	5
7	0

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

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

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

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

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

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

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

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

	5
7	0

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	75	18	95	79	29	98
2	5	INF	81	30	0	59	67
3	90	18	INF	65	89	81	19
4	69	18	6	INF	32	6	67
5	59	24	94	20	INF	5	61
6	76	16	81	16	43	INF	34
7	39	79	27	20	22	97	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	62
2	0	INF	81	30	0	59	49
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	43
5	49	19	89	15	INF	0	38
6	55	0	65	0	27	INF	0
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	7	0	2	77

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

	1	2	3	4	5	6	7
1	INF	75	18	95	79	29	98
2	5	INF	81	30	0	59	67
3	90	18	INF	65	89	81	19
4	69	18	6	INF	32	6	67
5	59	24	94	20	INF	5	61
6	76	16	81	16	43	INF	34
7	39	79	27	20	22	97	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	62
2	0	INF	81	30	0	59	49
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	43
5	49	19	89	15	INF	0	38
6	55	0	65	0	27	INF	0
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	7	0	2	77

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	75	18	95	79	29	98
2	5	INF	81	30	0	59	67
3	90	18	INF	65	89	81	19
4	69	18	6	INF	32	6	67
5	59	24	94	20	INF	5	61
6	76	16	81	16	43	INF	34
7	39	79	27	20	22	97	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	62
2	0	INF	81	30	0	59	49
3	67	0	INF	47	71	63	INF
4	58	12	0	INF	26	0	43
5	49	19	89	15	INF	0	38
6	55	0	65	0	27	INF	0
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6	7
1	INF	57	0	77	61	11	79
2	0	INF	81	30	0	59	66
3	67	0	INF	47	71	63	0
4	58	12	0	INF	26	0	60
5	49	19	89	15	INF	0	55
6	55	0	65	0	27	INF	17
7	14	59	7	0	2	77	INF

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	7	0	2	77

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77

	1	2	3	4	5	6
1	INF	57	0	77	61	11
2	0	INF	81	30	0	59
4	58	12	0	INF	26	0
5	49	19	89	15	INF	0
6	55	0	65	0	27	INF
7	14	59	INF	0	2	77