Maximal path problem

Given oriented unweighted graph and the problem is to find simple path开发者_C百科 of maximal length (start vertex and end vertex are not fixed). It obviously can be solved in O(n^2 * 2 ^n) but I heard that there is O(n * 2 ^ n) algorithm which I don't know. So how to solve it in O(n * 2 ^n)? //n = |V|

If your problem really is the Longest Path Problem on a DAG, the algorithm from Wikipedia is below and runs in 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))