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

Источник

Источник

Источник

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

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

12345
1
2
3
4
5

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

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

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

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

Время:0.0027949810028076

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

12345
1INF52798851
20INF458731
33569INF5737
4407825INF43
536731678INF

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

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

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

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

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

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

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

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

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

12345
1INF028150
20INF456531
3033INF02
415520INF18
52056040INF

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

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

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

Максимумы по строкам:33 31 15 15 20

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

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

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

12345
1INF028150
20INF456531
3033INF02
415520INF18
52056040INF

(1:2)

Поиск циклов

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

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

12345
1INFINF28150
20INF456531
3033INF02
415520INF18
52056040INF

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

12345
1INFINF28150
20INF456531
3033INF02
415520INF18
52056040INF

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

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

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

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

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

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

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

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

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

12345
1INFINF28150
20INF456531
300INF02
415190INF18
52023040INF

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

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

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

Максимумы по строкам:17 31 19 15 20

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

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

12345
1INF028150
20INF456531
3033INF02
415520INF18
52056040INF

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

1345
20456531
30INF02
4150INF18
520040INF

Поиск циклов

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

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

1345
2INF456531
30INF02
4150INF18
520040INF

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

1345
2INF456531
30INF02
4150INF18
520040INF

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

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

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

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

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

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

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

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

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

1345
2INF14340
30INF02
4150INF18
520040INF

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

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

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

Максимумы по строкам:16 34 15 20

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

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

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

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

1345
2INF14340
30INF02
4150INF18
520040INF

(3:4)

Поиск циклов

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

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

1345
2INF14340
30INFINF2
4150INF18
520040INF

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

1345
2INF14340
30INFINF2
4150INF18
520040INF

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

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

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

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

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

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

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

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

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

1345
2INF1400
30INFINF2
4150INF18
52006INF

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

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

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

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

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

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

1345
2INF14340
30INF02
4150INF18
520040INF

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

135
2INF140
415018
5200INF

Поиск циклов

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

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

135
2INF140
415INF18
5200INF

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

135
2INF140
415INF18
5200INF

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

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

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

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

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

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

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

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

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

135
2INF140
40INF3
5200INF

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

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

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

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

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

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

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

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

12345
1INFINF28150
20INF456531
300INF02
415190INF18
52023040INF

(2:1)

Поиск циклов

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

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

12345
1INFINF28150
2INFINF456531
300INF02
415190INF18
52023040INF

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

12345
1INFINF28150
2INFINF456531
300INF02
415190INF18
52023040INF

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

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

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

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

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

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

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

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

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

12345
1INFINF28150
2INFINF14340
300INF02
415190INF18
52023040INF

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

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

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

Максимумы по строкам:15 14 19 15 20

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

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

12345
1INFINF28150
20INF456531
300INF02
415190INF18
52023040INF

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

2345
1INF28150
30INF02
4190INF18
523040INF

Поиск циклов

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

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

2345
1INF28150
30INF02
4190INF18
523040INF

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

2345
1INF28150
30INF02
4190INF18
523040INF

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

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

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

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

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

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

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

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

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

2345
1INF28150
30INF02
4190INF18
523040INF

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

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

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

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

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

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

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

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

2345
1INF28150
30INF02
4190INF18
523040INF

(5:3)

Поиск циклов

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

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

2345
1INF28150
30INF02
4190INF18
523INF40INF

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

2345
1INF28150
30INF02
4190INF18
523INF40INF

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

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

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

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

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

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

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

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

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

2345
1INF28150
30INF02
4190INF18
50INF17INF

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

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

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

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

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

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

2345
1INF28150
30INF02
4190INF18
523040INF

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

245
1INF150
3002
419INF18

Поиск циклов

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

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

245
1INF150
300INF
419INF18

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

245
1INF150
300INF
419INF18

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

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

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

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

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

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

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

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

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

245
1INF150
300INF
41INF0

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

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

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

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

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

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

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

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

135
2INF140
40INF3
5200INF

(5:3)

Поиск циклов

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

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

135
2INF140
40INF3
520INFINF

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

135
2INF140
40INF3
520INFINF

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

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

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

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

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

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

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

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

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

135
2INF00
40INF3
50INFINF

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

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

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

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

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

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

135
2INF140
40INF3
5200INF

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

15
2INF0
403

Поиск циклов

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

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

15
2INF0
403

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

15
2INF0
403

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

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

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

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

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

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

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

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

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

15
2INF0
403

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

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

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

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

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

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

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

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

15
2INF0
403

(2:5)

Поиск циклов

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

Поиск циклов

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

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

15
2INFINF
40INF

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

15
2INFINF
40INF

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

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

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

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

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

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

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

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

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

15
2INFINF
40INF

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

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

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

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

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

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

15
2INF0
403

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

1
40

Поиск циклов

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

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

1
40

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

1
40

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

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

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

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

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

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

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

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

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

1
40

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

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

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

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

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

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

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

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

1
40

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

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