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