Вы можете решить это за O (n + m) время (где n - количество узлов, а m - количество ребер), используя топологическую сортировку. Начните с топологической сортировки обратного графа, чтобы все узлы были упорядочены таким образом, чтобы ни один узел не был посещен до того, как будут посещены все его дочерние элементы.
Теперь мы будем маркировать все узлы весом пути с наибольшим весом, начиная с этого узла. Это сделано на основе следующего рекурсивного наблюдения:
- Вес пути с наибольшим весом, начинающегося с узла приемника (любой узел без исходящих ребер) равен нулю, поскольку единственный путь, начинающийся с этого узла, - это путь нулевой длины только этого узла.
- Вес пути с наибольшим весом, начинающимся с любого другого узла, определяется как максимальный вес любого пути, образованного путем следования к исходящему ребру к узлу, а затем выбора пути максимального веса из этого узла.
Поскольку у нас есть узлы, отсортированные по обратной топологии, мы можем посетить все узлы в порядке, который гарантирует, что если мы когда-нибудь попробуем следовать по ребру и посмотрим стоимость самого тяжелого пути в конечной точке этого узла, мы будет уже рассчитан путь максимального веса, начиная с этого узла. Это означает, что, когда у нас будет обратный топологический порядок сортировки, мы можем применить следующий алгоритм ко всем узлам в этом порядке:
- Если узел не имеет исходящих ребер, запишите вес самого тяжелого пути, начинающегося в этом узле (обозначается d (u)), как ноль.
- В противном случае для каждого ребра (u, v), покидающего текущий узел u, вычислите l (u, v) + d (v) и задайте d (u) как наибольшее значение, полученное таким образом.
После того, как мы выполнили этот шаг, мы можем сделать один последний проход по всем узлам и вернуть наибольшее значение d, достигнутое любым узлом.
Время выполнения этого алгоритма можно проанализировать следующим образом. Вычисление топологической сортировки может быть выполнено за O (n + m) раз с использованием множества различных методов. Когда мы затем просматриваем каждый узел и каждое исходящее ребро от каждого узла, мы посещаем каждый узел и ребро ровно один раз. Это означает, что мы тратим O (n) времени на узлы и O (m) время на ребрах. Наконец, мы тратим O (n) времени на один последний проход по элементам, чтобы найти путь с наибольшим весом, который занимает O (n). Это дает общее время O (n + m), которое является линейным по размеру ввода.