最大経路問題

Question

与えられた重み付けされていないグラフを与え、最大長さの単純なパスを見つけることは です（開始頂点と終了頂点は固定されません）。明らかにO（n^2 * 2^n）で解くことができますが、わからないO（n * 2^n）アルゴリズムがあると聞きました。だから、それをO（n * 2^n）で解く方法は？ // n = | V |

Answer 1

あなたの問題は本当にDAGにLongest Path Problemであれば、ウィキペディアからのアルゴリズムは以下であると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))