Проблема максимального пути

Question

Для данного ориентированного невзвешенного графа задача состоит в том, чтобы найти простой путь максимальной длины (начальная и конечная вершины не фиксированы).Это, очевидно, может быть решено в O (n ^ 2 * 2 ^ n), но я слышал, что есть алгоритм O (n * 2 ^ n), которого я не знаю.Так как решить это в O (n * 2 ^ n)?// n = | V |

Answer 1

Если вашей проблемой действительно является Проблема с самым длинным путем на DAG , алгоритм из Википедии приведен ниже и работает в O (| V | + | E |):

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