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