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