NetworkX找到DAG中最長路徑的最有效方法，無錯誤

-1

從某個頂點開始，如何找到相對於該頂點的最長路徑？我一直在瀏覽所有內容，無法找到解決這個問題的方法，這個問題實際上適用於所有可能的DAG案例。 NetworkX中的源代碼將是首選，但是普通的python也可以。我真的很好奇，爲什麼我無法找到任何適當的工作示例，我明白這是一個NP型問題，但我想知道它的最有效的方式。NetworkX找到DAG中最長路徑的最有效方法，無錯誤

來源

2016-09-25 tohnotakaki

歡迎來到Stack Overflow！你似乎在要求某人爲你寫一些代碼。堆棧溢出是一個問答網站，而不是代碼寫入服務。請[see here]（http://stackoverflow.com/help/how-to-ask）學習如何編寫有效的問題。 – JGreenwell

首先，我會檢查這個圖是否連接。如果是這樣，那麼最長的路徑是跨所有節點的路徑。如果不是，則表示該頂點包含在連接的組件中。然後，我將使用connected_component_subgraphs來查找此頂點所在的最大組件。之後，最長路徑是此最大組件中所有節點之間的路徑。

當然，只有在您的路徑中不允許循環時纔有效。

import networkx as nx 
G = nx.DiGraph() 
G.add_edges_from([(0,1),(0,4),(4,5),(4,6),(5,6),(6,1),(0,2),(2,3),(1,2)]) 
for path in nx.all_simple_paths(G, source=0, target=3): 
    print(path)

結果：

[0, 1, 2, 3] 
[0, 2, 3] 
[0, 4, 5, 6, 1, 2, 3] 
[0, 4, 6, 1, 2, 3]

第三個是你喜歡什麼。

來源

2016-09-25 12:52:32 mengg

我明白這背後的邏輯，但我已經嘗試了很長時間來嘗試解決這個問題，我處於一個需要學習正確源代碼的地步 – tohnotakaki

請注意，我也想知道一個非常高效的這樣做的方式，暴力強制路徑不是我想要做的。我想要一個源代碼沿着更高效的「蠻力」的路線，也就是計算從頂點開始的某條路徑，並且如果頂點碰巧在另一個迭代中被發現，我們可以通過添加當前路徑到已經計算好的路徑 – tohnotakaki

我認爲NetworkX中的所有圖搜索算法都是通過強力。我也不明白爲什麼'dfs_tree'不能滿足你的需求。 – mengg

NetworkX找到DAG中最長路徑的最有效方法，無錯誤

回答

相關問題