-2

ここで、有向巡回グラフで最長の単純なパスを見つける方法 (パスが無限になるのを避けるために、各ノードが 1 回だけ訪問されるという単純な意味) を検索し、このようなソリューションに出くわしました。ただし、私が見つけたそのようなソリューションはすべて、そのパスに含まれる実際のノードではなく、最長パスの長さを計算する方法のみを示しています。

したがって、私の質問は、最長パスに含まれるノードを抽出するように、そのようなアルゴリズムをどのように変更できるでしょうか? Floyd-Warshall の全ペア最短パス アルゴリズムを変更して、パスの再構築を可能にする方法と同様です。

4

2 に答える 2

3

実際のパスを見つけるために必要なのは、最長距離のパスを追跡することだけです (このパスは前任者から取得します)。The longest path of vj= the longest path among precedessors U {vj}

方法は次のとおりです。

  • トポロジー順序付けを行うv1 > v2 >... > vn..
  • 任意の頂点をピックvj...
  • dist( vj) を から までの最長距離とv1しvjます。次に、dist( vj)=max(dist( u1)+1,dist( u2)+1,...,dist( uk)+1) ここで、u1,u2,...,ukは の前身ですvj。
  • path(vj)=path(ui)U{vj}whereuiは最大長の前任者 (つまり、 dist( vj) で選択したもの) です。
  • ごとにこれを計算しますvj。
  • 最長パスは、dist(vj)実際のパスの最大値ですpath(vj)。
于 2014-11-15T05:01:58.513 に答える
0

次のアルゴリズムは、深さ優先検索を使用して最長パスを見つけるために機能すると思います。** の間の問題は、DFS アルゴリズムの変更です。

DFS(G)
  For each u  V[G]
   {done(u)=0;
    Pre(u)=NULL;}
  Time=0;  
  For each uV[G]
   If done(u) == 0
   {**longest(u)=0**;
    DFS_VISIT(u);}

DFS_VISIT(u)
Done(u)=-1;
Discover(u)=time++;
For each v adjacent to u
If done(v)==0
    { pre(v)=u;
      **Longest(v)=longest(u)+1**;
      DFS_VISIT(v);}
Done(u)=1;
Finish(u)=time++`

すべての longest(v) を見つけた後、最大値を検索し、それが最長パスであると結論付けることができます。@Xlineどう思いますか

于 2016-03-20T00:04:04.593 に答える