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

-2

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

因此，我的问题是如何修改像that这样的算法，以便提取最长路径中涉及的节点？类似于Floyd-Warshall所有对最短路径算法可能是modified to allow path reconstruction。

来源

2014-11-14 LogicChains

您链接的问题中接受的答案可以进行简单修改以记录路径及其长度。 – 2014-11-14 14:17:57

@j_random_hacker怎么样？也许这对你来说微不足道，但它不是我的，所以我问了这个问题。 – LogicChains 2014-11-15 01:28:40

什么时候'path'改变了？每当它发生时，也更新路径中的节点列表。什么时候'bestPath'改变？将它重写为if语句：现在，在该语句的主体中，可以在更新其长度的同时更新当前最佳路径中的节点列表。 – 2014-11-15 02:18:29

要找到实际的路径，您只需要跟踪最长距离路径（从前辈获得此路径）。 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}其中ui是最大长度的前身（即我们在dist中选择的那个（vj））。
每vj计算一次。
最长的路径是dist(vj)的最大路径，实际路径为path(vj)。

来源

2014-11-15 05:01:58 Xline

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

来源

2016-03-20 00:04:04 StevieG

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

回答

相关问题