Самый длинный ациклический путь в направленном невзвешенном графике

Ответ 1

Динамическое программирование. Он также ссылается на Самая длинная проблема пути, учитывая, что это DAG.

Следующий код из Википедии:

algorithm dag-longest-path is
    input: 
         Directed acyclic graph G
    output: 
         Length of the longest path

    length_to = array with |V(G)| elements of type int with default value 0

    for each vertex v in topOrder(G) do
        for each edge (v, w) in E(G) do
            if length_to[w] <= length_to[v] + weight(G,(v,w)) then
                length_to[w] = length_to[v] + weight(G, (v,w))

    return max(length_to[v] for v in V(G))

Ответ 2

Пока график ацикличен, все, что вам нужно сделать, - это отрицать веса ребер и запускать любой алгоритм кратчайшего пути.

EDIT: Очевидно, вам нужен алгоритм кратчайшего пути, поддерживающий отрицательные веса. Кроме того, алгоритм из Википедии, похоже, имеет лучшую временную сложность, но я оставлю свой ответ здесь для справки.

Ответ 3

В Википедии есть алгоритм: http://en.wikipedia.org/wiki/Longest_path_problem

Похоже, что они используют весовые коэффициенты, но должны работать с весами, установленными на 1.

Ответ 4

Может быть решена методом критического пути:
1. Найти топологическое упорядочение
2. Найдите критический путь см. [Horowitz 1995], Основы структур данных на С++, Computer Science Press, Нью-Йорк.

Жадная стратегия (например, Дейкстра) не будет работать, не важно: 1. используйте "max" вместо "min" 2. преобразуйте положительные веса в отрицательные 3. дайте очень большое число M и используйте M-w как вес.