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

Источник

Источник

Источник

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

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

12345
1
2
3
4
5

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

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

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

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

Время:0.0026719570159912

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

12345
1INF4019849
236INF27171
3293INF9145
474190INF56
555387733INF

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

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

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

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

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

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

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

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

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

12345
1INF340975
235INF26027
3086INF890
402983INF6
5220440INF

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

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

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

Максимумы по строкам:31 26 5 6 29

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

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

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

12345
1INF340975
235INF26027
3086INF890
402983INF6
5220440INF

(1:3)

Поиск циклов

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

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

12345
1INF34INF975
235INF26027
3086INF890
402983INF6
5220440INF

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

12345
1INF34INF975
235INF26027
3086INF890
402983INF6
5220440INF

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

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

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

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

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

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

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

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

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

12345
1INF29INF920
235INF0027
3086INF890
402957INF6
5220180INF

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

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

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

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

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

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

12345
1INF340975
235INF26027
3086INF890
402983INF6
5220440INF

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

1245
235INF027
3086890
4029INF6
52200INF

Поиск циклов

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

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

1245
235INF027
3INF86890
4029INF6
52200INF

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

1245
235INF027
3INF86890
4029INF6
52200INF

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

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

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

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

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

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

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

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

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

1245
235INF027
3INF86890
4029INF6
52200INF

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

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

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

Максимумы по строкам:27 92 28 29

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

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

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

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

1245
235INF027
3INF86890
4029INF6
52200INF

(3:5)

Поиск циклов

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

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

1245
235INF027
3INF8689INF
4029INF6
52200INF

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

1245
235INF027
3INF8689INF
4029INF6
52200INF

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

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

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

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

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

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

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

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

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

1245
235INF021
3INF03INF
4029INF0
52200INF

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

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

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

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

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

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

1245
235INF027
3INF86890
4029INF6
52200INF

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

124
235INF0
4029INF
52200

Поиск циклов

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

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

124
235INF0
4029INF
52200

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

124
235INF0
4029INF
52200

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

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

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

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

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

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

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

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

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

124
235INF0
4029INF
52200

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

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

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

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

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

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

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

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

124
235INF0
4029INF
52200

(4:1)

Поиск циклов

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

Поиск циклов

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

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

124
235INF0
4INF29INF
5INF00

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

124
235INF0
4INF29INF
5INF00

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

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

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

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

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

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

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

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

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

124
20INF0
4INF0INF
5INF00

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

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

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

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

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

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

124
235INF0
4029INF
52200

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

24
2INF0
500

Поиск циклов

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

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

24
2INF0
500

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

24
2INF0
500

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

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

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

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

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

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

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

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

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

24
2INF0
500

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

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

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

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

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

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

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

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

24
2INF0
500

(2:4)

Поиск циклов

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

Поиск циклов

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

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

24
2INFINF
50INF

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

24
2INFINF
50INF

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

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

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

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

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

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

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

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

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

24
2INFINF
50INF

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

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

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

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

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

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

24
2INF0
500

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

2
50

Поиск циклов

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

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

2
50

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

2
50

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

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

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

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

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

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

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

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

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

2
50

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

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

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

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

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

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

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

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

2
50

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

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