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