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

Источник

Источник

Источник

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

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

123
1
2
3

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

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

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

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

Время:0.0025339126586914

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

123
1INF7257
299INF5
37032INF

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

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

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

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

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

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

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

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

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

123
1INF150
256INF0
300INF

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

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

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

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

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

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

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

123
1INF150
256INF0
300INF

(2:3)

Поиск циклов

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

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

123
1INF150
256INFINF
300INF

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

123
1INF150
256INFINF
300INF

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

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

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

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

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

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

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

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

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

123
1INF150
20INFINF
300INF

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

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

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

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

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

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

123
1INF150
256INF0
300INF

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

12
1INF15
300

Поиск циклов

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

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

12
1INF15
30INF

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

12
1INF15
30INF

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

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

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

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

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

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

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

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

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

12
1INF0
30INF

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

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

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

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

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

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

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

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

12
1INF0
30INF

(1:2)

Поиск циклов

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

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

12
1INFINF
30INF

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

12
1INFINF
30INF

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

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

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

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

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

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

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

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

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

12
1INFINF
30INF

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

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

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

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

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

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

12
1INF0
30INF

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

1
30

Поиск циклов

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

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

1
30

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

1
30

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

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

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

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

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

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

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

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

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

1
30

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

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

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

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

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

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

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

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

1
30

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

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