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