python - NetworkX 最有效的方法来在起始顶点处找到 DAG 中的最长路径且没有错误

Question

从某个顶点开始，如何找到相对于该顶点的最长路径？我一直在浏览，但找不到这个问题的解决方案，它实际上适用于所有可能的 DAG 案例。NetworkX 中的源代码将是首选，但常规 python 也可以。我真的很好奇为什么我无法找到任何合适的工作示例，我确实理解这是一个 NP 类型的问题，但我想知道最有效的方法。

Answer 1

首先，我会检查此图是否已连接。如果是这样，那么最长的路径是跨所有节点的路径。如果不是，则表示该顶点包含在连通分量中。然后我会用它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]

第三个是你喜欢的。