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

Question

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

Answer 1

Dynamic programming. Он также упоминается в Longest path problem, учитывая, что он является 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)) 

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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