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

Источник

Источник

Источник

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

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

123
1
2
3

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

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

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

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

Время:0.0024220943450928

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

123
1INF2720
211INF15
32028INF

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

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

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

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

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

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

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

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

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

123
1INF00
20INF4
301INF

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

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

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

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

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

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

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

123
1INF00
20INF4
301INF

(1:3)

Поиск циклов

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

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

123
1INF0INF
20INF4
301INF

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

123
1INF0INF
20INF4
301INF

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

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

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

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

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

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

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

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

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

123
1INF0INF
20INF0
301INF

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

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

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

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

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

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

123
1INF00
20INF4
301INF

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

12
20INF
301

Поиск циклов

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

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

12
20INF
3INF1

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

12
20INF
3INF1

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

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

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

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

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

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

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

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

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

12
20INF
3INF0

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

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

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

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

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

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

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

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

12
20INF
3INF0

(2:1)

Поиск циклов

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

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

12
2INFINF
3INF0

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

12
2INFINF
3INF0

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

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

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

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

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

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

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

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

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

12
2INFINF
3INF0

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

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

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

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

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

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

12
20INF
3INF0

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

2
30

Поиск циклов

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

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

2
30

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

2
30

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

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

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

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

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

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

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

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

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

2
30

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

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

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

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

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

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

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

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

2
30

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

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