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

Источник

Источник

Источник

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

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

123456
1
2
3
4
5
6

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

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

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

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

Время:0.0025520324707031

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

123456
1INF20455371
281INF9038337
35934INF102033
4729775INF9767
546818518INF88
69474274796INF

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

Мнимальные по строкам:1 7 10 67 18 27

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

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

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

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

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

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

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

123456
1INF0354260
269INF8331160
3445INF0023
40118INF200
52344670INF70
6622802059INF

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

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

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

Максимумы по строкам:5 16 16 23 23 23

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

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

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

123456
1INF0354260
269INF8331160
3445INF0023
40118INF200
52344670INF70
6622802059INF

(4:1)

Поиск циклов

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

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

123456
1INF0354260
269INF8331160
3445INF0023
4INF118INF200
52344670INF70
6622802059INF

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

123456
1INF0354260
269INF8331160
3445INF0023
4INF118INF200
52344670INF70
6622802059INF

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

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

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

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

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

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

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

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

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

123456
1INF0354260
246INF8331160
3215INF0023
4INF118INF200
5044670INF70
6392802059INF

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

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

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

Максимумы по строкам:5 16 16 8 21 23

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

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

123456
1INF0354260
269INF8331160
3445INF0023
40118INF200
52344670INF70
6622802059INF

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

23456
10354260
2INF8331160
35INF0023
544670INF70
62802059INF

Поиск циклов

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

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

23456
103INF260
2INF8331160
35INF0023
544670INF70
62802059INF

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

23456
103INF260
2INF8331160
35INF0023
544670INF70
62802059INF

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

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

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

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

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

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

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

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

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

23456
103INF260
2INF8331160
35INF0023
544670INF70
62802059INF

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

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

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

Максимумы по строкам:5 16 16 44 23

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

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

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

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

23456
103INF260
2INF8331160
35INF0023
544670INF70
62802059INF

(5:4)

Поиск циклов

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

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

23456
103INF260
2INF8331160
35INF0023
54467INFINF70
62802059INF

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

23456
103INF260
2INF8331160
35INF0023
54467INFINF70
62802059INF

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

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

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

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

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

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

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

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

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

23456
103INF260
2INF8331160
35INF0023
5023INFINF26
62802059INF

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

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

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

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

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

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

23456
103INF260
2INF8331160
35INF0023
544670INF70
62802059INF

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

2356
103260
2INF83160
35INF023
628059INF

Поиск циклов

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

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

2356
103260
2INF83160
35INF023
628059INF

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

2356
103260
2INF83160
35INF023
628059INF

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

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

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

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

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

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

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

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

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

2356
103260
2INF83160
35INF023
628059INF

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

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

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

Максимумы по строкам:5 16 21 31

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

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

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

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

2356
103260
2INF83160
35INF023
628059INF

(6:3)

Поиск циклов

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

Поиск циклов

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

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

2356
103INF0
2INF83160
35INF023
628INF59INF

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

2356
103INF0
2INF83160
35INF023
628INF59INF

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

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

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

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

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

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

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

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

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

2356
100INF0
2INF80160
35INF023
60INF31INF

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

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

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

Максимумы по строкам:80 16 21 31

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

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

2356
103260
2INF83160
35INF023
628059INF

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

256
10260
2INF160
35023

Поиск циклов

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

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

256
10INF0
2INF160
350INF

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

256
10INF0
2INF160
350INF

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

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

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

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

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

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

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

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

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

256
10INF0
2INF160
350INF

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

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

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

Максимумы по строкам:5 16 21

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

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

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

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

256
10INF0
2INF160
350INF

(3:5)

Поиск циклов

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

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

256
10INF0
2INF160
35INFINF

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

256
10INF0
2INF160
35INFINF

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

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

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

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

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

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

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

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

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

256
10INF0
2INF00
30INFINF

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

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

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

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

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

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

256
10INF0
2INF160
350INF

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

26
100
2INF0

Поиск циклов

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

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

26
100
2INF0

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

26
100
2INF0

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

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

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

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

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

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

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

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

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

26
100
2INF0

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

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

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

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

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

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

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

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

26
100
2INF0

(1:2)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

26
1INFINF
2INF0

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

26
1INFINF
2INF0

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

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

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

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

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

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

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

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

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

26
1INFINF
2INF0

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

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

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

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

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

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

26
100
2INF0

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

6
20

Поиск циклов

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

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

6
20

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

6
20

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

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

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

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

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

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

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

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

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

6
20

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

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

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

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

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

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

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

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

6
20

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

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