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

Источник

Источник

Источник

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

Отображать дерево

1234567
1
2
3
4
5
6
7

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

При клике на узел с номером обработки можно увидеть лог вычислений на данном этапе

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

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

Время:0.0032391548156738

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

1234567
1INF735084393855
21INF357084648
33764INF6868290
4235494INF933013
548115031INF4290
61867289193INF22
7328910178076INF

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

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

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

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

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

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

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

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

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

1234567
1INF3512460017
20INF346982637
33158INF0797684
4104181INF79170
53703920INF3179
6049107374INF4
72279076966INF

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

Подсчитанные степени у нулей:
(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)

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

1234567
1INF3512460017
20INF346982637
33158INF0797684
4104181INF79170
53703920INF3179
6049107374INF4
72279076966INF

(1:5)

Поиск циклов

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

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

1234567
1INF351246INF017
20INF346982637
33158INF0797684
4104181INF79170
53703920INF3179
6049107374INF4
72279076966INF

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

1234567
1INF351246INF017
20INF346982637
33158INF0797684
4104181INF79170
53703920INF3179
6049107374INF4
72279076966INF

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

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

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

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

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

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

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

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

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

1234567
1INF351246INF017
20INF346913637
33158INF0107684
4104181INF10170
53703920INF3179
604910735INF4
7227907066INF

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

Подсчитанные степени у нулей:
(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

1234567
1INF3512460017
20INF346982637
33158INF0797684
4104181INF79170
53703920INF3179
6049107374INF4
72279076966INF

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

123467
20INF3469637
33158INF07684
4104181INF170
537039203179
60491073INF4
722790766INF

Поиск циклов

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

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

123467
20INF3469637
33158INF07684
4104181INF170
5INF039203179
60491073INF4
722790766INF

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

123467
20INF3469637
33158INF07684
4104181INF170
5INF039203179
60491073INF4
722790766INF

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

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

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

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

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

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

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

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

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

123467
20INF3469467
33158INF05984
4104181INF00
5INF039201479
60491073INF4
722790749INF

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

Подсчитанные степени у нулей:
(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)

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

123467
20INF3469467
33158INF05984
4104181INF00
5INF039201479
60491073INF4
722790749INF

(5:2)

Поиск циклов

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

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

123467
20INF3469467
33158INF05984
4104181INF00
5INFINF39201479
60491073INF4
722790749INF

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

123467
20INF3469467
33158INF05984
4104181INF00
5INFINF39201479
60491073INF4
722790749INF

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

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

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

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

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

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

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

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

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

123467
20INF3469467
33117INF05984
410081INF00
5INFINF256065
6081073INF4
722380749INF

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

Подсчитанные степени у нулей:
(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

123467
20INF3469467
33158INF05984
4104181INF00
5INF039201479
60491073INF4
722790749INF

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

13467
203469467
331INF05984
41081INF00
601073INF4
7220749INF

Поиск циклов

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

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

13467
203469467
331INF05984
41081INF00
601073INF4
7220749INF

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

13467
203469467
331INF05984
41081INF00
601073INF4
7220749INF

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

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

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

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

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

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

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

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

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

13467
203469467
331INF05984
41081INF00
601073INF4
7220749INF

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

Подсчитанные степени у нулей:
(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)

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

13467
203469467
331INF05984
41081INF00
601073INF4
7220749INF

(4:6)

Поиск циклов

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

Поиск циклов

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

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

13467
2INF3469467
331INF05984
41081INFINF0
601073INF4
7220749INF

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

13467
2INF3469467
331INF05984
41081INFINF0
601073INF4
7220749INF

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

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

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

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

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

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

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

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

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

13467
2INF276200
331INF02084
41081INFINF0
601073INF4
7220710INF

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

Подсчитанные степени у нулей:
(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

13467
203469467
331INF05984
41081INF00
601073INF4
7220749INF

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

1347
2034697
331INF084
6010734
72207INF

Поиск циклов

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

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

1347
2INF34697
331INF084
6010INF4
72207INF

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

1347
2INF34697
331INF084
6010INF4
72207INF

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

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

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

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

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

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

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

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

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

1347
2INF27620
331INF084
6010INF4
72207INF

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

Подсчитанные степени у нулей:
(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)

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

1347
2INF27620
331INF084
6010INF4
72207INF

(3:4)

Поиск циклов

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

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

1347
2INF27620
331INFINF84
6010INF4
72207INF

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

1347
2INF27620
331INFINF84
6010INF4
72207INF

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

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

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

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

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

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

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

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

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

1347
2INF27550
30INFINF53
6010INF4
72200INF

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

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

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

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

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

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

1347
2INF27620
331INF084
6010INF4
72207INF

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

137
2INF270
60104
7220INF

Поиск циклов

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

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

137
2INF270
60104
7220INF

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

137
2INF270
60104
7220INF

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

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

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

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

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

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

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

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

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

137
2INF270
60104
7220INF

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

Подсчитанные степени у нулей:
(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)

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

137
2INF270
60104
7220INF

(7:3)

Поиск циклов

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

Поиск циклов

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

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

137
2INF270
60INF4
722INFINF

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

137
2INF270
60INF4
722INFINF

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

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

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

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

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

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

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

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

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

137
2INF00
60INF4
70INFINF

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

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

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

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

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

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

137
2INF270
60104
7220INF

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

17
2INF0
604

Поиск циклов

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

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

17
2INF0
604

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

17
2INF0
604

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

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

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

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

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

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

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

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

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

17
2INF0
604

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

Подсчитанные степени у нулей:
(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)

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

17
2INF0
604

(2:7)

Поиск циклов

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

Поиск циклов

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

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

17
2INFINF
60INF

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

17
2INFINF
60INF

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

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

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

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

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

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

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

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

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

17
2INFINF
60INF

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

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

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

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

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

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

17
2INF0
604

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

1
60

Поиск циклов

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

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

1
60

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

1
60

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

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

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

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

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

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

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

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

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

1
60

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

Подсчитанные степени у нулей:
(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
60

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

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