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

Question

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

Answer 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))

Answer 2

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

РЕДАКТИРОВАТЬ: Очевидно, вам нужен алгоритм кратчайшего пути, который поддерживает отрицательные веса. Кроме того, алгоритм из Википедии, кажется, имеет лучшую временную сложность, но я оставлю здесь свой ответ для справки.

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 как вес