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