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