如何在有向循環圖中找到最長的簡單路徑（包括所有中間節點）？

-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

如何在有向循環圖中找到最長的簡單路徑（包括所有中間節點）？

回答

相關問題