algorithm - 如何在有向循环图中找到最长的简单路径（包括所有中间节点）？

Question

我在这里搜索了如何在有向循环图中找到最长的简单路径（简单意味着每个节点只被访问一次，以避免路径无限），并且遇到了这样的解决方案。然而，我发现的所有此类解决方案仅显示如何计算最长路径的长度，而不是该路径中涉及的实际节点。

因此，我的问题是，如何修改这样的算法以提取最长路径中涉及的节点？类似于如何修改 Floyd-Warshall 全对最短路径算法以允许路径重建。

Answer 1

要找到实际路径，您只需要跟踪最长距离路径（您从前辈那里得到这条路径）。The longest path of vj= the longest path among precedessors U {vj}

方法如下：

• 做拓扑排序v1 > v2 >... > vn..
• 选择任何顶点vj...
• 令 dist( ) 为到vj的最长距离。那么 dist( )=max(dist( )+1,dist( )+1,...,dist( )+1) 其中是 的前身。v1vjvju1u2uku1,u2,...,ukvj
• path(vj)=path(ui)U{vj}哪里ui是具有最大长度的前任（即我们在 dist( vj) 中选择的那个）。
• 计算每个vj.
• 最长路径是dist(vj)实际路径的最大值path(vj)。

Answer 2

我想下面的算法可以使用深度优先搜索来找到最长的路径。** 之间的问题是对 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++`

在找到所有最长的（v）之后，我可以搜索最大值并得出结论它是最长的路径。你怎么看@Xline