NetworkX 가장 좋은 방법은 오류없이 시작점에서 DAG의 가장 긴 경로를 찾는 것입니다.

Question

특정 꼭지점부터 시작하여 그 꼭지점을 기준으로 가장 긴 경로를 찾는 방법은 무엇입니까? 나는 모든 것을 탐색 해 왔고 DAG의 모든 가능한 경우에 대해 실제로 작동하는이 문제에 대한 해결책을 찾을 수 없습니다. NetworkX의 소스 코드가 선호되지만 일반 파이썬도 좋습니다. 진정으로 호기심이 궁금해서 적절한 작업 예제를 찾을 수없는 이유는 그것이 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] 

세 번째는 당신이 좋아하는 것입니다.