Задача о самом длинном пути -- это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нем нет повторных вершин. В программе длина пути измеряется суммой весов ребер графа. Данная задача является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Задача решается за линейное время на ориентированных ациклических графах, которые мы и будем использовать в программе.
- Осуществить топологическую сортировку заданного ориентированного ациклического графа.
- Для каждой вершины v графа в топологической сортировке вычисляем длину самого длинного пути, завершающегося в вершине v путем просмотра входящих дуг от соседей и добавления веса ребра к максимальной длине в записях этих соседей.
- Начав с вершины v с самым большим записанным значением и проходя в обратном порядке, выбираем входящую дугу, у которой запись в начальной вершине имеет наибольшее значение.