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

Источник

Источник

Источник

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

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

123456
1
2
3
4
5
6

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

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

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

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

Время:0.0024199485778809

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

123456
1INF8897756427
246INF38876083
3630INF749272
4195012INF8661
585879014INF79
676717805INF

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

Мнимальные по строкам:27 38 6 12 14 5

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

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

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

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

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

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

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

123456
1INF377048370
28INF0492245
300INF688666
47140INF7449
57149760INF65
671422750INF

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

Подсчитанные степени у нулей:
(1:6)=82
(2:3)=8
(3:1)=7
(3:2)=14
(4:3)=7
(5:4)=97
(6:5)=24

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

Максимумы по строкам:82 8 14 7 97 24

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

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

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

123456
1INF377048370
28INF0492245
300INF688666
47140INF7449
57149760INF65
671422750INF

(5:4)

Поиск циклов

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

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

123456
1INF377048370
28INF0492245
300INF688666
47140INF7449
5714976INFINF65
671422750INF

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

123456
1INF377048370
28INF0492245
300INF688666
47140INF7449
5714976INFINF65
671422750INF

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

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

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

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

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

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

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

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

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

123456
1INF37700370
28INF012245
300INF208666
47140INF7449
522027INFINF16
671422270INF

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

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

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

Максимумы по строкам:16 1 7 7 16 24

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

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

123456
1INF377048370
28INF0492245
300INF688666
47140INF7449
57149760INF65
671422750INF

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

12356
1INF3770370
28INF02245
300INF8666
471407449
6714220INF

Поиск циклов

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

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

12356
1INF3770370
28INF02245
300INF8666
47140INF49
6714220INF

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

12356
1INF3770370
28INF02245
300INF8666
47140INF49
6714220INF

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

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

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

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

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

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

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

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

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

12356
1INF3770370
28INF02245
300INF8666
47140INF49
6714220INF

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

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

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

Максимумы по строкам:82 8 14 7 24

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

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

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

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

12356
1INF3770370
28INF02245
300INF8666
47140INF49
6714220INF

(1:6)

Поиск циклов

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

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

12356
1INF377037INF
28INF02245
300INF8666
47140INF49
6714220INF

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

12356
1INF377037INF
28INF02245
300INF8666
47140INF49
6714220INF

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

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

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

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

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

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

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

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

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

12356
1INF0330INF
28INF0220
300INF8621
47140INF4
6714220INF

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

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

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

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

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

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

12356
1INF3770370
28INF02245
300INF8666
47140INF49
6714220INF

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

1235
28INF022
300INF86
47140INF
6714220

Поиск циклов

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

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

1235
28INF022
300INF86
47140INF
6INF4220

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

1235
28INF022
300INF86
47140INF
6INF4220

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

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

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

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

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

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

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

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

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

1235
28INF022
300INF86
47140INF
6INF4220

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

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

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

Максимумы по строкам:8 14 7 24

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

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

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

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

1235
28INF022
300INF86
47140INF
6INF4220

(6:5)

Поиск циклов

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

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

1235
28INF022
300INF86
47140INF
6INF422INF

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

1235
28INF022
300INF86
47140INF
6INF422INF

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

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

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

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

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

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

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

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

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

1235
28INF00
300INF64
47140INF
6INF400INF

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

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

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

Максимумы по строкам:64 14 7 40

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

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

1235
28INF022
300INF86
47140INF
6INF4220

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

123
28INF0
300INF
47140

Поиск циклов

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

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

123
28INF0
300INF
47140

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

123
28INF0
300INF
47140

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

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

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

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

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

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

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

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

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

123
28INF0
300INF
47140

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

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

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

Максимумы по строкам:8 14 7

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

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

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

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

123
28INF0
300INF
47140

(3:2)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

123
28INF0
30INFINF
4INF140

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

123
28INF0
30INFINF
4INF140

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

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

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

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

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

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

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

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

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

123
28INF0
30INFINF
4INF00

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

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

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

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

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

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

123
28INF0
300INF
47140

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

13
280
470

Поиск циклов

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

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

13
28INF
4INF0

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

13
28INF
4INF0

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

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

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

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

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

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

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

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

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

13
20INF
4INF0

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

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

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

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

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

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

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

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

13
20INF
4INF0

(2:1)

Поиск циклов

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

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

13
2INFINF
4INF0

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

13
2INFINF
4INF0

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

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

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

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

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

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

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

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

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

13
2INFINF
4INF0

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

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

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

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

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

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

13
20INF
4INF0

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

3
40

Поиск циклов

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

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

3
40

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

3
40

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

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

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

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

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

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

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

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

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

3
40

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

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

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

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

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

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

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

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

3
40

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

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