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

Источник

Источник

Источник

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

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

1234
1
2
3
4

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

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

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

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

Время:0.0022518634796143

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

1234
1INF621936
21INF5888
36679INF0
4542050INF

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

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

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

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

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

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

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

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

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

1234
1INF43017
20INF5787
36679INF0
434030INF

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

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

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

Максимумы по строкам:47 91 83 73

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

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

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

1234
1INF43017
20INF5787
36679INF0
434030INF

(2:1)

Поиск циклов

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

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

1234
1INF43017
2INFINF5787
36679INF0
434030INF

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

1234
1INF43017
2INFINF5787
36679INF0
434030INF

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

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

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

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

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

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

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

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

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

1234
1INF43017
2INFINF030
33279INF0
40030INF

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

Подсчитанные степени у нулей:
(1:3)=17
(2:3)=30
(3:4)=49
(4:1)=32
(4:2)=43

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

Максимумы по строкам:17 30 49 43

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

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

1234
1INF43017
20INF5787
36679INF0
434030INF

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

234
143017
379INF0
4030INF

Поиск циклов

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

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

234
1INF017
379INF0
4030INF

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

234
1INF017
379INF0
4030INF

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

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

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

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

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

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

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

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

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

234
1INF017
379INF0
4030INF

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

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

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

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

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

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

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

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

234
1INF017
379INF0
4030INF

(4:2)

Поиск циклов

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

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

234
1INF017
379INF0
4INF30INF

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

234
1INF017
379INF0
4INF30INF

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

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

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

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

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

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

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

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

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

234
1INF017
30INF0
4INF0INF

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

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

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

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

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

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

234
1INF017
379INF0
4030INF

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

34
1017
3INF0

Поиск циклов

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

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

34
1017
3INF0

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

34
1017
3INF0

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

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

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

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

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

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

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

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

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

34
1017
3INF0

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

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

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

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

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

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

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

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

34
1017
3INF0

(1:3)

Поиск циклов

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

Поиск циклов

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

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

34
1INFINF
3INF0

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

34
1INFINF
3INF0

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

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

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

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

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

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

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

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

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

34
1INFINF
3INF0

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

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

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

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

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

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

34
1017
3INF0

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

4
30

Поиск циклов

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

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

4
30

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

4
30

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

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

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

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

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

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

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

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

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

4
30

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

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

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

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

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

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

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

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

4
30

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

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