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