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

Источник

Источник

Источник

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

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

123
1
2
3

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

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

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

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

Время:0.0023679733276367

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

123
1INF6070
266INF73
34628INF

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

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

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

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

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

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

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

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

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

123
1INF03
20INF0
3180INF

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

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

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

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

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

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

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

123
1INF03
20INF0
3180INF

(2:1)

Поиск циклов

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

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

123
1INF03
2INFINF0
3180INF

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

123
1INF03
2INFINF0
3180INF

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

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

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

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

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

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

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

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

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

123
1INF03
2INFINF0
300INF

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

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

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

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

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

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

123
1INF03
20INF0
3180INF

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

23
103
30INF

Поиск циклов

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

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

23
1INF3
30INF

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

23
1INF3
30INF

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

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

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

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

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

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

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

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

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

23
1INF0
30INF

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

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

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

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

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

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

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

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

23
1INF0
30INF

(1:3)

Поиск циклов

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

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

23
1INFINF
30INF

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

23
1INFINF
30INF

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

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

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

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

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

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

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

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

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

23
1INFINF
30INF

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

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

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

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

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

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

23
1INF0
30INF

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

2
30

Поиск циклов

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

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

2
30

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

2
30

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

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

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

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

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

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

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

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

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

2
30

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

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

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

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

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

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

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

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

2
30

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

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