graph - 線形時間での有向非巡回無重みグラフの最長パス

Question

このようなグラフの最長パスを線形時間で見つけるにはどうすればよいですか:

3 -> 2

4 -> 3

2 -> 5

ここでの最長パスは 4 -> 3 -> 2 であることを知っています。したがって、3 つのベチクルがありますが、O(N) 時間でそれを見つける方法がわかりません。助けてください。前もって感謝します。

Answer 1

グラフをトップ ソートし、トポロジ的にソートされた順序で頂点を選択します。

For each vertex u
    For each edge (u,v)
       if(d[v] < d[u] + weight(u,v))
          d[v] = d[u] + weight(u,v) 

ここで、任意の頂点 u の d[u] は、ソースからの最長距離です。各頂点 u について、d[u] は最小値および d[source]=0 に初期化されます。

これは DAG であるため、各エッジを 1 回だけトラバースして緩和する必要があります。これは基本的に、最長パスのベルマン フォード アルゴリズムを簡略化したものです。