graph-algorithm - 最大経路問題

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