从某个顶点开始，如何找到相对于该顶点的最长路径？我一直在浏览，无法找到这个问题的解决方案，这个问题实际上适用于所有可能的DAG案例 . NetworkX中的源代码是首选，但常规的python也很好 . 我真的很好奇为什么我无法找到任何正确的工作示例，我确实理解这是一个NP型问题，但我想知道它最有效的方式 .
首先，我会检查这个图是否已连接 . 如果是，则最长路径是跨所有节点的路径 . 如果不是，则表示该顶点包含在连接的组件中 . 然后我会使用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]
第三个是你喜欢的 .
1 回答
首先，我会检查这个图是否已连接 . 如果是，则最长路径是跨所有节点的路径 . 如果不是，则表示该顶点包含在连接的组件中 . 然后我会使用connected_component_subgraphs来找到这个顶点所在的最大组件 . 之后，最长的路径是这个最大组件中所有节点的路径 .
当然，只有在路径中不允许循环时才有效 .
结果：
第三个是你喜欢的 .