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

Источник

Источник

Источник

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

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

1234
1
2
3
4

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

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

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

Ответ: путь:1=>4=>3=>2=>1 длина: 110

Время:0.0026280879974365

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

1234
1INF583759
216INF2788
3110INF40
4547935INF

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

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

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

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

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

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

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

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

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

1234
1INF2100
20INF1150
3110INF18
419440INF

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

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

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

Максимумы по строкам:18 22 32 19

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

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

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

1234
1INF2100
20INF1150
3110INF18
419440INF

(3:2)

Поиск циклов

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

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

1234
1INF2100
20INF1150
311INFINF18
419440INF

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

1234
1INF2100
20INF1150
311INFINF18
419440INF

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

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

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

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

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

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

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

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

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

1234
1INF000
20INF1150
30INFINF7
419230INF

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

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

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

Максимумы по строкам:23 11 7 19

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

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

1234
1INF2100
20INF1150
3110INF18
419440INF

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

134
1INF00
201150
4190INF

Поиск циклов

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

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

134
1INF00
20INF50
4190INF

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

134
1INF00
20INF50
4190INF

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

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

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

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

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

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

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

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

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

134
1INF00
20INF50
4190INF

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

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

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

Максимумы по строкам:50 69 19

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

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

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

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

134
1INF00
20INF50
4190INF

(2:1)

Поиск циклов

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

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

134
1INF00
2INFINF50
4190INF

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

134
1INF00
2INFINF50
4190INF

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

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

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

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

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

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

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

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

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

134
1INF00
2INFINF0
400INF

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

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

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

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

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

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

134
1INF00
20INF50
4190INF

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

34
100
40INF

Поиск циклов

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

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

34
100
40INF

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

34
100
40INF

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

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

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

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

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

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

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

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

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

34
100
40INF

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

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

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

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

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

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

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

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

34
100
40INF

(1:3)

Поиск циклов

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

Поиск циклов

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

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

34
1INF0
40INF

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

34
1INF0
40INF

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

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

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

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

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

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

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

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

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

34
1INF0
40INF

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

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

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

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

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

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

34
100
40INF

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

4
4INF

Поиск циклов

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

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

4
4INF

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

4
4INF

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

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

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

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

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

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

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

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

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

4
4INF

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

Подсчитанные степени у нулей:

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

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

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

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

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

34
1INF0
40INF

(1:4)

Поиск циклов

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

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

34
1INFINF
40INF

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

34
1INFINF
40INF

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

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

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

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

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

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

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

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

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

34
1INFINF
40INF

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

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

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

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

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

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

34
1INF0
40INF

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

3
40

Поиск циклов

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

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

3
40

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

3
40

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

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

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

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

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

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

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

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

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

3
40

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

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

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

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

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

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

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

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

3
40

добавили в путь 4:3

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