Решение: Самый длинный путь в графе
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого протяжённого пути из города А в город Л? Длиной пути считать количество дорог, составляющих этот путь.
Решение по шагам
3 шагаПредставим города и дороги в виде ориентированного графа. Для каждого города вычисляем длину самого длинного пути из города А.
При переходе по дороге из города $X$ в город $Y$ значение увеличивается на одну дорогу: $d(Y)=\max(d(Y),d(X)+1)$.
Последовательно просматривая вершины по направлению дорог и сравнивая все возможные пути, для города Л получаем максимальную длину, равную 6.
Где здесь ошибаются
Считать количество городов вместо количества дорог.
Переходить по дороге против направления стрелки.
Выбирать первый найденный путь, не сравнив его с остальными.