Решение: Длина пути в графе
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.
Решение по шагам
3 шагаПредставим города вершинами ориентированного графа, а дороги — его рёбрами. Двигаемся только по направлению стрелок.
Для каждой вершины вычисляем длину максимального пути из А: при переходе по одной дороге длина пути увеличивается на 1. Последовательно просматривая вершины схемы, получаем максимальную длину пути до города М.
Максимальное число дорог на пути из А в М равно 8.
Где здесь ошибаются
Считать количество городов вместо количества дорог.
Двигаться по дороге против направления стрелки.
Выбрать первый найденный путь, не сравнив его с остальными.