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